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