# Parity Hamiltonian path problem

Wikipedia says that Hamiltonian path problem is NPC, but Parity Hamiltonian path problem (i.e., is there an odd amount of hamiltonian path) is P. Does a reduction from, e.g., SAT, to HPP, unavoidably duplicate some solutions?

• @YuvalFilmus I guess #P-complete require any modulo, while Parity P only require modulo 2, which can be done by making every invalid move cancel with another(loop -> going through the loop in opposite direction, going back directly at a point -> going another)
– l4m2
Commented May 24, 2019 at 12:02
• I don't see where the Wikipedia article says anything at all about $\oplus\textsf{HamPath}$. Where are you getting that it's in $\mathrm{P}$? Commented May 24, 2019 at 12:15
• @DavidRicherby By providing a solution
– l4m2
Commented May 24, 2019 at 12:16
• I don't understand. Who provided a solution? Where is it? Commented May 24, 2019 at 12:18
• Determining the parity of the number of Hamiltonian cycles is ⊕P-complete, see Valiant. If the same holds for the closely related Hamiltonian paths, then we don't expect a polytime algorithm for your problem. Commented May 24, 2019 at 12:21