DLOG ∈ PWPP

Inclusion · HV21

Statement

HV21 define a total search problem over groupoids given by circuits: an instance describes a binary operation, a generator $g$ and a target $h$, and a solution is either an exponent $x$ with $g^x=h$ or a witness that the instance does not describe a cyclic group generated by $g$. This problem is complete for PWPP, and a variant of it, Index, is complete for PPP — HV21. On instances that are cyclic groups the only solutions are discrete logarithms, so DLOG over cyclic groups given by circuits lies in PWPP; completeness transfers only to the groupoid problem, not to DLOG on genuine cyclic groups — HV21. These answer an open question of SZZ18.

Notes

• Membership goes through a reduction to the problem General-Claw — HV21. The direct collision argument through $(x,y)\mapsto g^x{h}^y$ (DLOG ⇒ CRHF) extracts ${\log }_{g}h$ only in groups of prime order. In the group of order $6$ generated by $g=3$ modulo $7$, with $h=g^2=2$, the pairs $(0,0)$ and $(0,3)$ collide, but they give only $3{\log }_{g}h\equiv 0(\mathrm{mod}6)$, which $0$, $2$ and $4$ all satisfy — standard.
• Average-case hardness of other TFNP subclasses, such as PPAD, from discrete logarithms would need structure beyond what collision resistance provides — HV21.