Jump to content

coHAMPATH - why is it considered not in NP?


Recommended Posts

I understand that if you use the "has a polynomial time certificate" definition of NP, that the complement of the Hamiltonian path problem does not appear to be in NP - there is no certificate of polynomial size that a DTM could use to verify whether a given graph has no such paths. But, using the alternative definition of NP, which is those problems that can be solved in polynomial time by an NTM, doesn't it appear that coHAMPATH is in NP? My "proof" would go like this:

 

1. Give the NTM the description of the entire graph.

2. The NTM then nondeterministically checks every possible path to see if it is Hamiltonian. If any of the branches accept, then reject. If none of the branches accept, then accept.

 

It seems like this algorithm could run on an NTM in polynomial time, thought I can't think of a way to prove to a DTM that a graph has no Hamiltonian paths. Obviously I must be misunderstanding something here, I just don't know what.

Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
×
×
  • Create New...

Important Information

We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.