FAC ∈ PWPP (under randomized reductions)

Inclusion · Jer16

Statement

Factoring reduces in randomized polynomial time to Weak Pigeon, the complete problem of PWPP, so lies in PWPP under randomized reductions, and in deterministic polynomial time under the generalized Riemann hypothesis — Jer16.

Notes

• PWPP is contained in PPP (PWPP ⊆ PPP), and the discrete logarithm, in a suitable total formulation, is PWPP-complete (DLOG ∈ PWPP) — HV21.