Jump to content

vpoko

New Members
  • Content Count

    1
  • Joined

  • Last visited

Everything posted by vpoko

  1. 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
×
×
  • 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.