質問

I am having difficulty understanding the distinction between NP and Co-NP.

According to my textbook (Sipser), the HAMPATH problem is in NP. That is, for the language:
HAMPATH = { (G,s,t) | G is a directed graph with a Hamiltonian path from s to t}, there exists a nondeterministic Turing Machine M that can decide this problem in polynomial time. I understood this to mean that for some input (G,s,t), M accepts if G has a Hamiltonian Path from s to t, and M rejects if G does not have a Hamiltonian Path from s to t, both in polynomial time.

However, the book also says that !HAMPATH = { (G,s,t) | G is a directed graph with no Hamiltonian path from s to t} is in Co-NP, so it is not known to be in NP.

Why couldn't the same NTM for HAMPATH be used to decide !HAMPATH, except that it returns the opposite state?

正しい解決策はありません

ライセンス: CC-BY-SA帰属
所属していません cs.stackexchange
scroll top