Mixing
Proving Hamiltonian Cycle is NP Complete
$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.
algorithms computational-complexity np-complete hamiltonian-path
edited Jan 14 at 18:00
Upc
488314
asked Aug 3 '14 at 14:37
technotechno
3222826
$endgroup$
add a comment |
$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.
algorithms computational-complexity np-complete hamiltonian-path
edited Jan 14 at 18:00
Upc
488314
asked Aug 3 '14 at 14:37
technotechno
3222826
$endgroup$
$begingroup$
See cs.stackexchange.com/questions/9556/… .
$endgroup$
– Kyle Jones
Aug 3 '14 at 17:20
add a comment |
$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.
algorithms computational-complexity np-complete hamiltonian-path
edited Jan 14 at 18:00
Upc
488314
asked Aug 3 '14 at 14:37
technotechno
3222826
$endgroup$
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.
algorithms computational-complexity np-complete hamiltonian-path
algorithms computational-complexity np-complete hamiltonian-path
edited Jan 14 at 18:00
Upc
488314
asked Aug 3 '14 at 14:37
technotechno
3222826
edited Jan 14 at 18:00
Upc
488314
asked Aug 3 '14 at 14:37
technotechno
3222826
edited Jan 14 at 18:00
Upc
488314
edited Jan 14 at 18:00
Upc
488314
edited Jan 14 at 18:00
Upc
488314
488314
asked Aug 3 '14 at 14:37
technotechno
3222826
asked Aug 3 '14 at 14:37
technotechno
3222826
asked Aug 3 '14 at 14:37
technotechno
3222826
3222826
$begingroup$
See cs.stackexchange.com/questions/9556/… .
$endgroup$
– Kyle Jones
Aug 3 '14 at 17:20
add a comment |
$begingroup$
See cs.stackexchange.com/questions/9556/… .
$endgroup$
– Kyle Jones
Aug 3 '14 at 17:20
$begingroup$
See cs.stackexchange.com/questions/9556/… .
$endgroup$
– Kyle Jones
Aug 3 '14 at 17:20
$begingroup$
See cs.stackexchange.com/questions/9556/… .
$endgroup$
– Kyle Jones
Aug 3 '14 at 17:20
add a comment |
3 Answers
3
active
oldest
votes
$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
|
show 5 more comments
$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 $xin LLeftrightarrow exists yin{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.
answered Aug 3 '14 at 15:18
zarathustrazarathustra
4,12511029
$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
add a comment |
$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.
answered Oct 6 '17 at 13:43
CSstudentCSstudent
111
$endgroup$
$begingroup$
Thanks for your answer.
$endgroup$
– techno
Oct 6 '17 at 14:01
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f886334%2fproving-hamiltonian-cycle-is-np-complete%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
$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
|
show 5 more comments
$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
|
show 5 more comments
$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$
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.
edited Aug 3 '14 at 16:45
community wiki
2 revs
MJD
$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
|
show 5 more comments
$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
$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
$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
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 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$
@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$
@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
$begingroup$
@techno To prove what?
$endgroup$
– MJD
Aug 4 '14 at 12:37
|
show 5 more comments
$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 $xin LLeftrightarrow exists yin{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.
answered Aug 3 '14 at 15:18
zarathustrazarathustra
4,12511029
$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
add a comment |
$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 $xin LLeftrightarrow exists yin{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.
answered Aug 3 '14 at 15:18
zarathustrazarathustra
4,12511029
$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
add a comment |
$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 $xin LLeftrightarrow exists yin{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.
answered Aug 3 '14 at 15:18
zarathustrazarathustra
4,12511029
$endgroup$
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 $xin LLeftrightarrow exists yin{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.
answered Aug 3 '14 at 15:18
zarathustrazarathustra
4,12511029
edited Aug 3 '14 at 17:07
answered Aug 3 '14 at 15:18
zarathustrazarathustra
4,12511029
answered Aug 3 '14 at 15:18
zarathustrazarathustra
4,12511029
answered Aug 3 '14 at 15:18
zarathustrazarathustra
4,12511029
4,12511029
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
add a comment |
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
1
$begingroup$
Thanks.. but kind of complex explanation at-least for me
$endgroup$
– techno
Aug 3 '14 at 15:42
$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$
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$
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
$begingroup$
Sure,it would help other people who are looking deeper :)
$endgroup$
– techno
Aug 3 '14 at 17:12
add a comment |
$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.
answered Oct 6 '17 at 13:43
CSstudentCSstudent
111
$endgroup$
$begingroup$
Thanks for your answer.
$endgroup$
– techno
Oct 6 '17 at 14:01
add a comment |
$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.
answered Oct 6 '17 at 13:43
CSstudentCSstudent
111
$endgroup$
$begingroup$
Thanks for your answer.
$endgroup$
– techno
Oct 6 '17 at 14:01
add a comment |
$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.
answered Oct 6 '17 at 13:43
CSstudentCSstudent
111
$endgroup$
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.
answered Oct 6 '17 at 13:43
CSstudentCSstudent
111
answered Oct 6 '17 at 13:43
CSstudentCSstudent
111
answered Oct 6 '17 at 13:43
CSstudentCSstudent
111
answered Oct 6 '17 at 13:43
CSstudentCSstudent
111
111
$begingroup$
Thanks for your answer.
$endgroup$
– techno
Oct 6 '17 at 14:01
add a comment |
$begingroup$
Thanks for your answer.
$endgroup$
– techno
Oct 6 '17 at 14:01
$begingroup$
Thanks for your answer.
$endgroup$
– techno
Oct 6 '17 at 14:01
$begingroup$
Thanks for your answer.
$endgroup$
– techno
Oct 6 '17 at 14:01
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f886334%2fproving-hamiltonian-cycle-is-np-complete%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
$begingroup$
See cs.stackexchange.com/questions/9556/… .
$endgroup$
– Kyle Jones
Aug 3 '14 at 17:20