Relation between Undecidable problems and NP-Hard
up vote
1
down vote
favorite
I drew these pictures to check whether I comprehended the ideas of P, NP, NP Complete and NP Hard correctly.
And then, I realized that it is not certain where undecidable problems should be placed.
Did I draw the pictures correctly? (Are all the undecidable problems including the halting problem are NP-Hard when P=NP, and some of them are so when P≠NP?)
I asked this to professor, but he said that undecidable problems including the Halting problem are not NP Hard because they are not solvable, which is a contrast to many answers in Stack exchange.
And one more thing, when P≠NP, are there problems which are neither NP nor NP Hard? If so, are they undecidable problems too? (Highlighted with a blue line in the second picture)
complexity-theory computability undecidability np-hard
edited 1 hour ago
Raphael♦
57.2k23139311
asked 4 hours ago
Riddle Aaron
133
add a comment |
up vote
1
down vote
favorite
I drew these pictures to check whether I comprehended the ideas of P, NP, NP Complete and NP Hard correctly.
And then, I realized that it is not certain where undecidable problems should be placed.
Did I draw the pictures correctly? (Are all the undecidable problems including the halting problem are NP-Hard when P=NP, and some of them are so when P≠NP?)
I asked this to professor, but he said that undecidable problems including the Halting problem are not NP Hard because they are not solvable, which is a contrast to many answers in Stack exchange.
And one more thing, when P≠NP, are there problems which are neither NP nor NP Hard? If so, are they undecidable problems too? (Highlighted with a blue line in the second picture)
complexity-theory computability undecidability np-hard
edited 1 hour ago
Raphael♦
57.2k23139311
asked 4 hours ago
Riddle Aaron
133
For me, i ageee with your teacher. If you can't solve with Turing machine in not polinomial time, you can't prove that problems are in NP (or better in NP hard).
– theantomc
2 hours ago
I disagree - NP-hardness does not require the set to be decidable. I think the confusion was that NP sets (including NP-complete sets) have to be decidable.
– sdcvvc
54 mins ago
add a comment |
up vote
1
down vote
favorite
up vote
1
down vote
favorite
I drew these pictures to check whether I comprehended the ideas of P, NP, NP Complete and NP Hard correctly.
And then, I realized that it is not certain where undecidable problems should be placed.
Did I draw the pictures correctly? (Are all the undecidable problems including the halting problem are NP-Hard when P=NP, and some of them are so when P≠NP?)
I asked this to professor, but he said that undecidable problems including the Halting problem are not NP Hard because they are not solvable, which is a contrast to many answers in Stack exchange.
And one more thing, when P≠NP, are there problems which are neither NP nor NP Hard? If so, are they undecidable problems too? (Highlighted with a blue line in the second picture)
complexity-theory computability undecidability np-hard
edited 1 hour ago
Raphael♦
57.2k23139311
asked 4 hours ago
Riddle Aaron
133
I drew these pictures to check whether I comprehended the ideas of P, NP, NP Complete and NP Hard correctly.
And then, I realized that it is not certain where undecidable problems should be placed.
Did I draw the pictures correctly? (Are all the undecidable problems including the halting problem are NP-Hard when P=NP, and some of them are so when P≠NP?)
I asked this to professor, but he said that undecidable problems including the Halting problem are not NP Hard because they are not solvable, which is a contrast to many answers in Stack exchange.
And one more thing, when P≠NP, are there problems which are neither NP nor NP Hard? If so, are they undecidable problems too? (Highlighted with a blue line in the second picture)
complexity-theory computability undecidability np-hard
complexity-theory computability undecidability np-hard
edited 1 hour ago
Raphael♦
57.2k23139311
asked 4 hours ago
Riddle Aaron
133
edited 1 hour ago
Raphael♦
57.2k23139311
asked 4 hours ago
Riddle Aaron
133
edited 1 hour ago
Raphael♦
57.2k23139311
edited 1 hour ago
Raphael♦
57.2k23139311
edited 1 hour ago
Raphael♦
57.2k23139311
57.2k23139311
asked 4 hours ago
Riddle Aaron
133
asked 4 hours ago
Riddle Aaron
133
asked 4 hours ago
Riddle Aaron
133
133
For me, i ageee with your teacher. If you can't solve with Turing machine in not polinomial time, you can't prove that problems are in NP (or better in NP hard).
– theantomc
2 hours ago
I disagree - NP-hardness does not require the set to be decidable. I think the confusion was that NP sets (including NP-complete sets) have to be decidable.
– sdcvvc
54 mins ago
add a comment |
For me, i ageee with your teacher. If you can't solve with Turing machine in not polinomial time, you can't prove that problems are in NP (or better in NP hard).
– theantomc
2 hours ago
I disagree - NP-hardness does not require the set to be decidable. I think the confusion was that NP sets (including NP-complete sets) have to be decidable.
– sdcvvc
54 mins ago
For me, i ageee with your teacher. If you can't solve with Turing machine in not polinomial time, you can't prove that problems are in NP (or better in NP hard).
– theantomc
2 hours ago
For me, i ageee with your teacher. If you can't solve with Turing machine in not polinomial time, you can't prove that problems are in NP (or better in NP hard).
– theantomc
2 hours ago
I disagree - NP-hardness does not require the set to be decidable. I think the confusion was that NP sets (including NP-complete sets) have to be decidable.
– sdcvvc
54 mins ago
I disagree - NP-hardness does not require the set to be decidable. I think the confusion was that NP sets (including NP-complete sets) have to be decidable.
– sdcvvc
54 mins ago
add a comment |
2 Answers
2
active
oldest
votes
up vote
2
down vote
I believe that this answer by Yuval Filmus all the questions you have asked.
If P=NP then any non-trivial set is NP-hard (other than the empty set and the complete set), so assume P$neq$NP. If $A$ is a set and $f_i$ reduces SAT to $A$ in polytime, then $f_i$ must have infinite range. Otherwise, we can hardcode the relevant values of $f_i$ to get a polytime algorithm for SAT.
We can construct an undecidable problem which is not NP-hard using diagonalization. Let $f_i$ be an enumeration of all polytime reductions whose range is infinite. We construct an undecidable problem $A$ such that no $f_i$ reduces SAT to $A$. We will use $K$ to denote the undecidable set corresponding to the halting problem.
The set $A$ will be defined in stages, starting with a completely undefined set. In stage $i$, we find a string $s$ such that $f_i(s)$ is longer than any string on which $A$ is defined (here we use the fact that the range of $f_i$ is infinite). We define $A$ on $f_i(s)$ so that $s in SAT$ iff $f_i(s) notin A$. After all finite stages, we complete the definition of $A$ for each undefined string $s$ by letting $s in A$ iff $|s| in K$.
By construction, no polytime $f_i$ reduces SAT to $A$, and so $A$ is not NP-hard. On the other hand, $A$ is not decidable since $K$ reduces to $A$: we can decide whether $n in K$ (for $n geq 2$) by taking a majority of three strings of length $n$.
To summarize,
- Halting problem is NP-hard.
- If $Pne NP$, not all undecidable problems are NP-hard.
- If $P = NP$, all non-trivial sets are NP-hard.
answered 1 hour ago
Alex Smart
514
+1, I'd like to add that point 1 holds under the normal binary encoding of the halting problem; the unary encoding is not NP-hard, unless P=NP.
– sdcvvc
55 mins ago
"not all undecidable problems are NP-hard" means that there are some undecidable problems are not in NP-hard, and that means P≠NP because if P=NP, all problems are NP-hard. So I think that we do not know whether "not all undecidable problems are NP-hard" before we solve P-NP problem. Am I correct?
– Riddle Aaron
40 mins ago
@RiddleAaron That sounds right.
– Alex Smart
33 mins ago
add a comment |
up vote
1
down vote
NP-Hard means "at least as hard as the hardest problems in NP"! Hence, all the problems such as halting problem which is not decidable, is in NP-Hard but not in NP. See this page.
There are decision problems that are NP-hard but not NP-complete, for example the halting problem.
answered 2 hours ago
OmG
1,233412
add a comment |
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
2
down vote
I believe that this answer by Yuval Filmus all the questions you have asked.
If P=NP then any non-trivial set is NP-hard (other than the empty set and the complete set), so assume P$neq$NP. If $A$ is a set and $f_i$ reduces SAT to $A$ in polytime, then $f_i$ must have infinite range. Otherwise, we can hardcode the relevant values of $f_i$ to get a polytime algorithm for SAT.
We can construct an undecidable problem which is not NP-hard using diagonalization. Let $f_i$ be an enumeration of all polytime reductions whose range is infinite. We construct an undecidable problem $A$ such that no $f_i$ reduces SAT to $A$. We will use $K$ to denote the undecidable set corresponding to the halting problem.
The set $A$ will be defined in stages, starting with a completely undefined set. In stage $i$, we find a string $s$ such that $f_i(s)$ is longer than any string on which $A$ is defined (here we use the fact that the range of $f_i$ is infinite). We define $A$ on $f_i(s)$ so that $s in SAT$ iff $f_i(s) notin A$. After all finite stages, we complete the definition of $A$ for each undefined string $s$ by letting $s in A$ iff $|s| in K$.
By construction, no polytime $f_i$ reduces SAT to $A$, and so $A$ is not NP-hard. On the other hand, $A$ is not decidable since $K$ reduces to $A$: we can decide whether $n in K$ (for $n geq 2$) by taking a majority of three strings of length $n$.
To summarize,
- Halting problem is NP-hard.
- If $Pne NP$, not all undecidable problems are NP-hard.
- If $P = NP$, all non-trivial sets are NP-hard.
answered 1 hour ago
Alex Smart
514
+1, I'd like to add that point 1 holds under the normal binary encoding of the halting problem; the unary encoding is not NP-hard, unless P=NP.
– sdcvvc
55 mins ago
"not all undecidable problems are NP-hard" means that there are some undecidable problems are not in NP-hard, and that means P≠NP because if P=NP, all problems are NP-hard. So I think that we do not know whether "not all undecidable problems are NP-hard" before we solve P-NP problem. Am I correct?
– Riddle Aaron
40 mins ago
@RiddleAaron That sounds right.
– Alex Smart
33 mins ago
add a comment |
up vote
2
down vote
I believe that this answer by Yuval Filmus all the questions you have asked.
If P=NP then any non-trivial set is NP-hard (other than the empty set and the complete set), so assume P$neq$NP. If $A$ is a set and $f_i$ reduces SAT to $A$ in polytime, then $f_i$ must have infinite range. Otherwise, we can hardcode the relevant values of $f_i$ to get a polytime algorithm for SAT.
We can construct an undecidable problem which is not NP-hard using diagonalization. Let $f_i$ be an enumeration of all polytime reductions whose range is infinite. We construct an undecidable problem $A$ such that no $f_i$ reduces SAT to $A$. We will use $K$ to denote the undecidable set corresponding to the halting problem.
The set $A$ will be defined in stages, starting with a completely undefined set. In stage $i$, we find a string $s$ such that $f_i(s)$ is longer than any string on which $A$ is defined (here we use the fact that the range of $f_i$ is infinite). We define $A$ on $f_i(s)$ so that $s in SAT$ iff $f_i(s) notin A$. After all finite stages, we complete the definition of $A$ for each undefined string $s$ by letting $s in A$ iff $|s| in K$.
By construction, no polytime $f_i$ reduces SAT to $A$, and so $A$ is not NP-hard. On the other hand, $A$ is not decidable since $K$ reduces to $A$: we can decide whether $n in K$ (for $n geq 2$) by taking a majority of three strings of length $n$.
To summarize,
- Halting problem is NP-hard.
- If $Pne NP$, not all undecidable problems are NP-hard.
- If $P = NP$, all non-trivial sets are NP-hard.
answered 1 hour ago
Alex Smart
514
+1, I'd like to add that point 1 holds under the normal binary encoding of the halting problem; the unary encoding is not NP-hard, unless P=NP.
– sdcvvc
55 mins ago
"not all undecidable problems are NP-hard" means that there are some undecidable problems are not in NP-hard, and that means P≠NP because if P=NP, all problems are NP-hard. So I think that we do not know whether "not all undecidable problems are NP-hard" before we solve P-NP problem. Am I correct?
– Riddle Aaron
40 mins ago
@RiddleAaron That sounds right.
– Alex Smart
33 mins ago
add a comment |
up vote
2
down vote
up vote
2
down vote
I believe that this answer by Yuval Filmus all the questions you have asked.
If P=NP then any non-trivial set is NP-hard (other than the empty set and the complete set), so assume P$neq$NP. If $A$ is a set and $f_i$ reduces SAT to $A$ in polytime, then $f_i$ must have infinite range. Otherwise, we can hardcode the relevant values of $f_i$ to get a polytime algorithm for SAT.
We can construct an undecidable problem which is not NP-hard using diagonalization. Let $f_i$ be an enumeration of all polytime reductions whose range is infinite. We construct an undecidable problem $A$ such that no $f_i$ reduces SAT to $A$. We will use $K$ to denote the undecidable set corresponding to the halting problem.
The set $A$ will be defined in stages, starting with a completely undefined set. In stage $i$, we find a string $s$ such that $f_i(s)$ is longer than any string on which $A$ is defined (here we use the fact that the range of $f_i$ is infinite). We define $A$ on $f_i(s)$ so that $s in SAT$ iff $f_i(s) notin A$. After all finite stages, we complete the definition of $A$ for each undefined string $s$ by letting $s in A$ iff $|s| in K$.
By construction, no polytime $f_i$ reduces SAT to $A$, and so $A$ is not NP-hard. On the other hand, $A$ is not decidable since $K$ reduces to $A$: we can decide whether $n in K$ (for $n geq 2$) by taking a majority of three strings of length $n$.
To summarize,
- Halting problem is NP-hard.
- If $Pne NP$, not all undecidable problems are NP-hard.
- If $P = NP$, all non-trivial sets are NP-hard.
answered 1 hour ago
Alex Smart
514
I believe that this answer by Yuval Filmus all the questions you have asked.
If P=NP then any non-trivial set is NP-hard (other than the empty set and the complete set), so assume P$neq$NP. If $A$ is a set and $f_i$ reduces SAT to $A$ in polytime, then $f_i$ must have infinite range. Otherwise, we can hardcode the relevant values of $f_i$ to get a polytime algorithm for SAT.
We can construct an undecidable problem which is not NP-hard using diagonalization. Let $f_i$ be an enumeration of all polytime reductions whose range is infinite. We construct an undecidable problem $A$ such that no $f_i$ reduces SAT to $A$. We will use $K$ to denote the undecidable set corresponding to the halting problem.
The set $A$ will be defined in stages, starting with a completely undefined set. In stage $i$, we find a string $s$ such that $f_i(s)$ is longer than any string on which $A$ is defined (here we use the fact that the range of $f_i$ is infinite). We define $A$ on $f_i(s)$ so that $s in SAT$ iff $f_i(s) notin A$. After all finite stages, we complete the definition of $A$ for each undefined string $s$ by letting $s in A$ iff $|s| in K$.
By construction, no polytime $f_i$ reduces SAT to $A$, and so $A$ is not NP-hard. On the other hand, $A$ is not decidable since $K$ reduces to $A$: we can decide whether $n in K$ (for $n geq 2$) by taking a majority of three strings of length $n$.
To summarize,
- Halting problem is NP-hard.
- If $Pne NP$, not all undecidable problems are NP-hard.
- If $P = NP$, all non-trivial sets are NP-hard.
answered 1 hour ago
Alex Smart
514
answered 1 hour ago
Alex Smart
514
answered 1 hour ago
Alex Smart
514
answered 1 hour ago
Alex Smart
514
514
+1, I'd like to add that point 1 holds under the normal binary encoding of the halting problem; the unary encoding is not NP-hard, unless P=NP.
– sdcvvc
55 mins ago
"not all undecidable problems are NP-hard" means that there are some undecidable problems are not in NP-hard, and that means P≠NP because if P=NP, all problems are NP-hard. So I think that we do not know whether "not all undecidable problems are NP-hard" before we solve P-NP problem. Am I correct?
– Riddle Aaron
40 mins ago
@RiddleAaron That sounds right.
– Alex Smart
33 mins ago
add a comment |
+1, I'd like to add that point 1 holds under the normal binary encoding of the halting problem; the unary encoding is not NP-hard, unless P=NP.
– sdcvvc
55 mins ago
"not all undecidable problems are NP-hard" means that there are some undecidable problems are not in NP-hard, and that means P≠NP because if P=NP, all problems are NP-hard. So I think that we do not know whether "not all undecidable problems are NP-hard" before we solve P-NP problem. Am I correct?
– Riddle Aaron
40 mins ago
@RiddleAaron That sounds right.
– Alex Smart
33 mins ago
+1, I'd like to add that point 1 holds under the normal binary encoding of the halting problem; the unary encoding is not NP-hard, unless P=NP.
– sdcvvc
55 mins ago
+1, I'd like to add that point 1 holds under the normal binary encoding of the halting problem; the unary encoding is not NP-hard, unless P=NP.
– sdcvvc
55 mins ago
"not all undecidable problems are NP-hard" means that there are some undecidable problems are not in NP-hard, and that means P≠NP because if P=NP, all problems are NP-hard. So I think that we do not know whether "not all undecidable problems are NP-hard" before we solve P-NP problem. Am I correct?
– Riddle Aaron
40 mins ago
"not all undecidable problems are NP-hard" means that there are some undecidable problems are not in NP-hard, and that means P≠NP because if P=NP, all problems are NP-hard. So I think that we do not know whether "not all undecidable problems are NP-hard" before we solve P-NP problem. Am I correct?
– Riddle Aaron
40 mins ago
@RiddleAaron That sounds right.
– Alex Smart
33 mins ago
@RiddleAaron That sounds right.
– Alex Smart
33 mins ago
add a comment |
up vote
1
down vote
NP-Hard means "at least as hard as the hardest problems in NP"! Hence, all the problems such as halting problem which is not decidable, is in NP-Hard but not in NP. See this page.
There are decision problems that are NP-hard but not NP-complete, for example the halting problem.
answered 2 hours ago
OmG
1,233412
add a comment |
up vote
1
down vote
NP-Hard means "at least as hard as the hardest problems in NP"! Hence, all the problems such as halting problem which is not decidable, is in NP-Hard but not in NP. See this page.
There are decision problems that are NP-hard but not NP-complete, for example the halting problem.
answered 2 hours ago
OmG
1,233412
add a comment |
up vote
1
down vote
up vote
1
down vote
NP-Hard means "at least as hard as the hardest problems in NP"! Hence, all the problems such as halting problem which is not decidable, is in NP-Hard but not in NP. See this page.
There are decision problems that are NP-hard but not NP-complete, for example the halting problem.
answered 2 hours ago
OmG
1,233412
NP-Hard means "at least as hard as the hardest problems in NP"! Hence, all the problems such as halting problem which is not decidable, is in NP-Hard but not in NP. See this page.
There are decision problems that are NP-hard but not NP-complete, for example the halting problem.
answered 2 hours ago
OmG
1,233412
answered 2 hours ago
OmG
1,233412
answered 2 hours ago
OmG
1,233412
answered 2 hours ago
OmG
1,233412
1,233412
add a comment |
add a comment |
Thanks for contributing an answer to Computer Science 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.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- 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.
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%2fcs.stackexchange.com%2fquestions%2f101316%2frelation-between-undecidable-problems-and-np-hard%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
For me, i ageee with your teacher. If you can't solve with Turing machine in not polinomial time, you can't prove that problems are in NP (or better in NP hard).
– theantomc
2 hours ago
I disagree - NP-hardness does not require the set to be decidable. I think the confusion was that NP sets (including NP-complete sets) have to be decidable.
– sdcvvc
54 mins ago