Proving Hamiltonian Cycle is NP Complete

Question

I'm trying to learn Complexity classes.I want to show Hamiltonian cycle is NP Complete.

The text tells me that

Inorder to prove NP-Completeness we first show it belongs to NP,by taking a certificate. The certificate is a set of N vertices making up the Hamiltonian cycle.The verification algorithm then checks if there is an edge between each of these vertices.It can be done in polynomial time.

My question is how can we say that the verification algorithm completes in polynomial time and if it does then how does it prove Ham cycle belongs to NP.

I lack perspective,can anyone explain this in simple terms.

Answer 1

A language is in NP if a proposed solution can be verified in polynomial time. In this case a proposed solution is simply a listing of the vertices in the order they appear in the claimed cycle. This list is the so-called certificate.

To check if this list is actually a solution to the Hamiltonian cycle problem, one counts the vertices to make sure they are all there, then checks that each is connected to the next by an edge, and that the last is connected to the first.

This takes time proportional to $n$, because there are $n$ vertices to count and $n$ edges to check. $n$ is a polynomial, so the check runs in polynomial time.

Note that this only shows that Hamiltonian Cycle is in NP, not that it is NP-complete.

Answer 2

A language $L$ is in NP if there exists a Turing Machine $M$ that runs in polynomial time and a polynomial $p(n)$, such that $x\in L\Leftrightarrow \exists y\in\{0,1\}^{p(|x|)}. M(x,y) \text{ accepts}$. The $y$ in this formula is often called the certificate, and its size has to be polynomial in the size of $x$.

To prove that the Hamiltonian Cycle problem is in NP, one has to show that there exists a Turing Machine that works in polynomial time and such that given an instance $G$ (a graph) and a $y$, $M$ accepts iff $y$ "witnesses" that $G$ has a Hamiltonian cycle. The machine $M(G,y)$ does the following: it assumes that $y$ is a sequence of nodes in $G$. For each $v_i,v_{i+1}$ in this sequence, $M$ checks that there is an edge from $v_i$ to $v_{i+1}$ in $G$. If this is the case for all $i$ and if the last vertex is equal to the first one, and if the vertices of $G$ are in the list, $M(G,y)$ accepts, and otherwise it rejects.

Now see that:

• If $G=(V,E)$ has a Hamiltonian path, there indeed exists this sequence of vertices $(v_i)$, and it has size $|V|$ which is linear in the size of $G$, so that the implication $\Rightarrow$ above is true.
• Conversely, if there exists a $y$ such that $M(G,y)$ accepts, by the way $M$ works we can conclude that $G$ has indeed a Hamiltonian cycle.

It remains to see that the machine computes in polynomial time: if the sequence of vertices is $v_1,\ldots,v_m$, the machine does $m$ checks in $G$ to see if there is an edge. Such a check can be done in time $O(|E|)$ (very naively), so that overall the complexity of $M$ is $O(|E|m)$, which is polynomial in the size of the input. Hence, Hamiltonian Cycle is in NP.

Answer 3

First, P is not the opposite of NP and vice versa. P is polynomial time, and NP is non deterministic polynomial time. It means that, if a problem is P, then there exists a solution that runs in polynomial time (i.e. n^a, where a is constant) to solve that problem. While NP is the verification if a solution works. It's a decision problem, answered by yes or no in polynomial time. Example, we can verify that 1-2-3-4-1 is a solution to know if a graph is a Hamiltonian cycle. That is, we can easily verify that 1,2,3,4 are vertices of the graph and there exists edges that makes a cycle. But that doesn't mean that there exists a solution that FINDS the Hamiltonian cycle in polynomial time (especially when n approaches infinity). It belongs to the NP-hard problems, that makes it NP-complete.