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.

Sorry, I don't know about Hamiltonians and stuff

I'm not sure we have the expertise for this in Computer Science, so I'm going to pop it over to Applied Mathematics and see if anyone there can do anything with it.