1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ @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) $\endgroup$ – l4m2 May 24 at 12:02
  • 1
    $\begingroup$ 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}$? $\endgroup$ – David Richerby May 24 at 12:15
  • $\begingroup$ @DavidRicherby By providing a solution $\endgroup$ – l4m2 May 24 at 12:16
  • $\begingroup$ I don't understand. Who provided a solution? Where is it? $\endgroup$ – David Richerby May 24 at 12:18
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus May 24 at 12:21
1
$\begingroup$

As far as we know, there is no polynomial-time algorithm for HPP. Put differently, there is no known polynomial-time reduction from any NP-hard problem with the properties that you require to Parity-HPP.

If such a reduction did exist, we could reduce any NP-hard problem A to Parity-HPP (in polynomial time) and then solve A using the polynomial-time algorithm that you claim.

$\endgroup$
  • $\begingroup$ Fixed some mistake in problem I guess. Even no known way to reduce NP-hard problem into ⊕HPP, from ⊕NPC to ⊕HPP is also a huge affect(e.g. it factorizes integers). So why the way from NPC to HPP don't work here? $\endgroup$ – l4m2 May 24 at 10:54
  • $\begingroup$ @l4m2 No worries, I figured the reduction was intended the other way around. I have never attempted such a reduction so I don't where you would get stuck. But the bottom line is that we just don't know. Maybe if you try hard enough it can be done (but you shouldn't hold your breath to succeed). $\endgroup$ – Juho May 24 at 10:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.