Mixing
What will happen to NP-Hard problems if P=NP
Clash Royale CLAN TAG#URR8PPP
up vote
1
down vote
favorite
I was going through the lecture of prof. Erik Demaine and he said that a problem X is NP-Hard if it is at-least as hard as every problem Y that belongs to NP class.
He further said that if we can prove that there exists a problem that belongs to NP but not to P, then we can absolutely be sure that NP hard problems don't belong to P class.
Here is my question... What happens if P=NP. Thus it mean that all NP-hard problems become polynomially solvable? Will all NP hard problems reduce to polynomial order if P=NP?
complexity-theory np-complete np-hard np
edited 4 hours ago
Yuval Filmus
185k12175335
asked 5 hours ago
Abhilash Mishra
111
add a comment |Â
up vote
1
down vote
favorite
I was going through the lecture of prof. Erik Demaine and he said that a problem X is NP-Hard if it is at-least as hard as every problem Y that belongs to NP class.
He further said that if we can prove that there exists a problem that belongs to NP but not to P, then we can absolutely be sure that NP hard problems don't belong to P class.
Here is my question... What happens if P=NP. Thus it mean that all NP-hard problems become polynomially solvable? Will all NP hard problems reduce to polynomial order if P=NP?
complexity-theory np-complete np-hard np
edited 4 hours ago
Yuval Filmus
185k12175335
asked 5 hours ago
Abhilash Mishra
111
add a comment |Â
up vote
1
down vote
favorite
up vote
1
down vote
favorite
I was going through the lecture of prof. Erik Demaine and he said that a problem X is NP-Hard if it is at-least as hard as every problem Y that belongs to NP class.
He further said that if we can prove that there exists a problem that belongs to NP but not to P, then we can absolutely be sure that NP hard problems don't belong to P class.
Here is my question... What happens if P=NP. Thus it mean that all NP-hard problems become polynomially solvable? Will all NP hard problems reduce to polynomial order if P=NP?
complexity-theory np-complete np-hard np
edited 4 hours ago
Yuval Filmus
185k12175335
asked 5 hours ago
Abhilash Mishra
111
I was going through the lecture of prof. Erik Demaine and he said that a problem X is NP-Hard if it is at-least as hard as every problem Y that belongs to NP class.
He further said that if we can prove that there exists a problem that belongs to NP but not to P, then we can absolutely be sure that NP hard problems don't belong to P class.
Here is my question... What happens if P=NP. Thus it mean that all NP-hard problems become polynomially solvable? Will all NP hard problems reduce to polynomial order if P=NP?
complexity-theory np-complete np-hard np
complexity-theory np-complete np-hard np
edited 4 hours ago
Yuval Filmus
185k12175335
asked 5 hours ago
Abhilash Mishra
111
edited 4 hours ago
Yuval Filmus
185k12175335
asked 5 hours ago
Abhilash Mishra
111
edited 4 hours ago
Yuval Filmus
185k12175335
edited 4 hours ago
Yuval Filmus
185k12175335
edited 4 hours ago
Yuval Filmus
185k12175335
185k12175335
asked 5 hours ago
Abhilash Mishra
111
asked 5 hours ago
Abhilash Mishra
111
asked 5 hours ago
Abhilash Mishra
111
111
add a comment |Â
add a comment |Â
3 Answers
3
active
oldest
votes
up vote
3
down vote
No. A problem is Np-Hard if all NP problems are reducible to an instance of that problem in polynomial time. Some NP-Hard problems cannot be solved in nondeterministic polynomial time, and are not in NP. Then these problems will not be polynomial time solvable regardless of whether or not P=NP.
answered 4 hours ago
HackerBoss
2345
add a comment |Â
up vote
2
down vote
The halting problem is NP-hard: given any language $L$ in P accepted by some nondeterministic machine $M$, we can come up with a polytime reduction that on input $x$ constructs a Turing machine which runs $M$ on $x$ and all possible witnesses, halting if $M$ accepts any of them, and going into an infinite loop otherwise.
We know unconditionally that the halting problem is not computable, and so in particular, isn’t in P.
answered 4 hours ago
Yuval Filmus
185k12175335
add a comment |Â
up vote
0
down vote
So just as your Prof. wikipedia says (emphasis mine):
NP-hardness [...]is the defining property of a class of problems that are, informally, "at least as hard as the hardest problems in NP"
(Still Informally) you can think of the ‚at least‘ as:
NP $leq$ NP-Hard
So you have to distinguish those NP-hard problems for which the equality holds from those which are ,strictly‘ harder. I.e problems that are NP-hard and are also in NP (a.k.a NP-complete) vs problems which are NP-hard but not in NP.
Looking at it this way, it should be realtively easy to reason about your question. Namely, if P=NP:
- For problems that are NP-hard and are also in NP it will obviously mean they are also in P (since P=NP by assumption)
- For problems that are NP-hard but not in NP it will mean nothing.
This euler diagram from wikipedia might also help to clear things up
answered 1 hour ago
dingalapadum
1313
add a comment |Â
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
3
down vote
No. A problem is Np-Hard if all NP problems are reducible to an instance of that problem in polynomial time. Some NP-Hard problems cannot be solved in nondeterministic polynomial time, and are not in NP. Then these problems will not be polynomial time solvable regardless of whether or not P=NP.
answered 4 hours ago
HackerBoss
2345
add a comment |Â
up vote
3
down vote
No. A problem is Np-Hard if all NP problems are reducible to an instance of that problem in polynomial time. Some NP-Hard problems cannot be solved in nondeterministic polynomial time, and are not in NP. Then these problems will not be polynomial time solvable regardless of whether or not P=NP.
answered 4 hours ago
HackerBoss
2345
add a comment |Â
up vote
3
down vote
up vote
3
down vote
No. A problem is Np-Hard if all NP problems are reducible to an instance of that problem in polynomial time. Some NP-Hard problems cannot be solved in nondeterministic polynomial time, and are not in NP. Then these problems will not be polynomial time solvable regardless of whether or not P=NP.
answered 4 hours ago
HackerBoss
2345
No. A problem is Np-Hard if all NP problems are reducible to an instance of that problem in polynomial time. Some NP-Hard problems cannot be solved in nondeterministic polynomial time, and are not in NP. Then these problems will not be polynomial time solvable regardless of whether or not P=NP.
answered 4 hours ago
HackerBoss
2345
answered 4 hours ago
HackerBoss
2345
answered 4 hours ago
HackerBoss
2345
answered 4 hours ago
HackerBoss
2345
2345
add a comment |Â
add a comment |Â
up vote
2
down vote
The halting problem is NP-hard: given any language $L$ in P accepted by some nondeterministic machine $M$, we can come up with a polytime reduction that on input $x$ constructs a Turing machine which runs $M$ on $x$ and all possible witnesses, halting if $M$ accepts any of them, and going into an infinite loop otherwise.
We know unconditionally that the halting problem is not computable, and so in particular, isn’t in P.
answered 4 hours ago
Yuval Filmus
185k12175335
add a comment |Â
up vote
2
down vote
The halting problem is NP-hard: given any language $L$ in P accepted by some nondeterministic machine $M$, we can come up with a polytime reduction that on input $x$ constructs a Turing machine which runs $M$ on $x$ and all possible witnesses, halting if $M$ accepts any of them, and going into an infinite loop otherwise.
We know unconditionally that the halting problem is not computable, and so in particular, isn’t in P.
answered 4 hours ago
Yuval Filmus
185k12175335
add a comment |Â
up vote
2
down vote
up vote
2
down vote
The halting problem is NP-hard: given any language $L$ in P accepted by some nondeterministic machine $M$, we can come up with a polytime reduction that on input $x$ constructs a Turing machine which runs $M$ on $x$ and all possible witnesses, halting if $M$ accepts any of them, and going into an infinite loop otherwise.
We know unconditionally that the halting problem is not computable, and so in particular, isn’t in P.
answered 4 hours ago
Yuval Filmus
185k12175335
The halting problem is NP-hard: given any language $L$ in P accepted by some nondeterministic machine $M$, we can come up with a polytime reduction that on input $x$ constructs a Turing machine which runs $M$ on $x$ and all possible witnesses, halting if $M$ accepts any of them, and going into an infinite loop otherwise.
We know unconditionally that the halting problem is not computable, and so in particular, isn’t in P.
answered 4 hours ago
Yuval Filmus
185k12175335
answered 4 hours ago
Yuval Filmus
185k12175335
answered 4 hours ago
Yuval Filmus
185k12175335
answered 4 hours ago
Yuval Filmus
185k12175335
185k12175335
add a comment |Â
add a comment |Â
up vote
0
down vote
So just as your Prof. wikipedia says (emphasis mine):
NP-hardness [...]is the defining property of a class of problems that are, informally, "at least as hard as the hardest problems in NP"
(Still Informally) you can think of the ‚at least‘ as:
NP $leq$ NP-Hard
So you have to distinguish those NP-hard problems for which the equality holds from those which are ,strictly‘ harder. I.e problems that are NP-hard and are also in NP (a.k.a NP-complete) vs problems which are NP-hard but not in NP.
Looking at it this way, it should be realtively easy to reason about your question. Namely, if P=NP:
- For problems that are NP-hard and are also in NP it will obviously mean they are also in P (since P=NP by assumption)
- For problems that are NP-hard but not in NP it will mean nothing.
This euler diagram from wikipedia might also help to clear things up
answered 1 hour ago
dingalapadum
1313
add a comment |Â
up vote
0
down vote
So just as your Prof. wikipedia says (emphasis mine):
NP-hardness [...]is the defining property of a class of problems that are, informally, "at least as hard as the hardest problems in NP"
(Still Informally) you can think of the ‚at least‘ as:
NP $leq$ NP-Hard
So you have to distinguish those NP-hard problems for which the equality holds from those which are ,strictly‘ harder. I.e problems that are NP-hard and are also in NP (a.k.a NP-complete) vs problems which are NP-hard but not in NP.
Looking at it this way, it should be realtively easy to reason about your question. Namely, if P=NP:
- For problems that are NP-hard and are also in NP it will obviously mean they are also in P (since P=NP by assumption)
- For problems that are NP-hard but not in NP it will mean nothing.
This euler diagram from wikipedia might also help to clear things up
answered 1 hour ago
dingalapadum
1313
add a comment |Â
up vote
0
down vote
up vote
0
down vote
So just as your Prof. wikipedia says (emphasis mine):
NP-hardness [...]is the defining property of a class of problems that are, informally, "at least as hard as the hardest problems in NP"
(Still Informally) you can think of the ‚at least‘ as:
NP $leq$ NP-Hard
So you have to distinguish those NP-hard problems for which the equality holds from those which are ,strictly‘ harder. I.e problems that are NP-hard and are also in NP (a.k.a NP-complete) vs problems which are NP-hard but not in NP.
Looking at it this way, it should be realtively easy to reason about your question. Namely, if P=NP:
- For problems that are NP-hard and are also in NP it will obviously mean they are also in P (since P=NP by assumption)
- For problems that are NP-hard but not in NP it will mean nothing.
This euler diagram from wikipedia might also help to clear things up
answered 1 hour ago
dingalapadum
1313
So just as your Prof. wikipedia says (emphasis mine):
NP-hardness [...]is the defining property of a class of problems that are, informally, "at least as hard as the hardest problems in NP"
(Still Informally) you can think of the ‚at least‘ as:
NP $leq$ NP-Hard
So you have to distinguish those NP-hard problems for which the equality holds from those which are ,strictly‘ harder. I.e problems that are NP-hard and are also in NP (a.k.a NP-complete) vs problems which are NP-hard but not in NP.
Looking at it this way, it should be realtively easy to reason about your question. Namely, if P=NP:
- For problems that are NP-hard and are also in NP it will obviously mean they are also in P (since P=NP by assumption)
- For problems that are NP-hard but not in NP it will mean nothing.
This euler diagram from wikipedia might also help to clear things up
answered 1 hour ago
dingalapadum
1313
answered 1 hour ago
dingalapadum
1313
answered 1 hour ago
dingalapadum
1313
answered 1 hour ago
dingalapadum
1313
1313
add a comment |Â
add a comment |Â
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
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcs.stackexchange.com%2fquestions%2f99044%2fwhat-will-happen-to-np-hard-problems-if-p-np%23new-answer', 'question_page');
);
Post as a guest
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
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
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
