4
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks for the clear answer.But when an algorithm runs in polynomial time it belongs to the P Class right? How can you say that its in NP? $\endgroup$ – techno Aug 3 '14 at 17:13
  • 1
    $\begingroup$ @techno MJD described the verification process, which confirms that a proposed solution is correct. That is not the same thing as finding the solution itself. $\endgroup$ – Kyle Jones Aug 3 '14 at 17:30
  • $\begingroup$ @techno A problem is in $P$ if a deterministic Turing machine can find a solution in polynomial time. Being able to check a proposed solution in polynomial time does not help you find a solution in polynomial time if you are a deterministic turing machine. $\endgroup$ – MJD Aug 3 '14 at 21:54
  • $\begingroup$ @KyleJones and MVD.Thanks for the replies.So let me put it like this- The Hamiltonian problem is the problem of checking whether a given undirected graph contains a Hamiltonian cycle right? To prove this we take a certificate ie: a set of vertices that we already know to form an Hamiltonian cycle right? $\endgroup$ – techno Aug 4 '14 at 11:44
  • $\begingroup$ @techno To prove what? $\endgroup$ – MJD Aug 4 '14 at 12:37
1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Thanks.. but kind of complex explanation at-least for me $\endgroup$ – techno Aug 3 '14 at 15:42
  • $\begingroup$ im a noob when it comes to algorithms.Explanation in layman's term would be preferred like the other answer,so that i can understand. $\endgroup$ – techno Aug 3 '14 at 17:08
  • $\begingroup$ MJD's answer is very clear, you are right. I will leave my answer nonetheless, as it is more formal on what NP is. $\endgroup$ – zarathustra Aug 3 '14 at 17:11
  • $\begingroup$ Sure,it would help other people who are looking deeper :) $\endgroup$ – techno Aug 3 '14 at 17:12
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks for your answer. $\endgroup$ – techno Oct 6 '17 at 14:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.