always even, so if one Hamiltonian cycle is given, then a second one must also exist. However, finding this second cycle does not seem to be an easy computational task. Papadimitriou defined the complexity class PPA to encapsulate problems such as this one.

Polynomial time verifier

The Hamiltonian path problem is NP meaning a proposed solution can be verified in polynomial time.

1.Previous
3.Next