Prove a problem that is NP-hard and not NP-complete in not in P
up vote
0
down vote
favorite
If A is not NP-hard, but not NP-complete, then prove that A in not in P.
A is NP-hard if there is an NP-complete problem B such that B is reducible to A in polynomial time. A is NP-complete if A is in NP and all NP problems are reducible to A in polynomial time. But A is not NP-complete, so one one or both of those conditions must be false. If A is not in NP, then A is not in P. The other case is that there exists at least one NP problem that is not reducible to A in polynomial time. This is where I am stuck. How do I get from knowing that there is an NP-complete problem that is reducible and an NP problem that is not reducible to A is not in P?
np np-complete np-hard
asked Nov 11 at 16:41
AdamK
72118
add a comment |
up vote
0
down vote
favorite
If A is not NP-hard, but not NP-complete, then prove that A in not in P.
A is NP-hard if there is an NP-complete problem B such that B is reducible to A in polynomial time. A is NP-complete if A is in NP and all NP problems are reducible to A in polynomial time. But A is not NP-complete, so one one or both of those conditions must be false. If A is not in NP, then A is not in P. The other case is that there exists at least one NP problem that is not reducible to A in polynomial time. This is where I am stuck. How do I get from knowing that there is an NP-complete problem that is reducible and an NP problem that is not reducible to A is not in P?
np np-complete np-hard
asked Nov 11 at 16:41
AdamK
72118
add a comment |
up vote
0
down vote
favorite
up vote
0
down vote
favorite
If A is not NP-hard, but not NP-complete, then prove that A in not in P.
A is NP-hard if there is an NP-complete problem B such that B is reducible to A in polynomial time. A is NP-complete if A is in NP and all NP problems are reducible to A in polynomial time. But A is not NP-complete, so one one or both of those conditions must be false. If A is not in NP, then A is not in P. The other case is that there exists at least one NP problem that is not reducible to A in polynomial time. This is where I am stuck. How do I get from knowing that there is an NP-complete problem that is reducible and an NP problem that is not reducible to A is not in P?
np np-complete np-hard
asked Nov 11 at 16:41
AdamK
72118
If A is not NP-hard, but not NP-complete, then prove that A in not in P.
A is NP-hard if there is an NP-complete problem B such that B is reducible to A in polynomial time. A is NP-complete if A is in NP and all NP problems are reducible to A in polynomial time. But A is not NP-complete, so one one or both of those conditions must be false. If A is not in NP, then A is not in P. The other case is that there exists at least one NP problem that is not reducible to A in polynomial time. This is where I am stuck. How do I get from knowing that there is an NP-complete problem that is reducible and an NP problem that is not reducible to A is not in P?
np np-complete np-hard
np np-complete np-hard
asked Nov 11 at 16:41
AdamK
72118
asked Nov 11 at 16:41
AdamK
72118
asked Nov 11 at 16:41
AdamK
72118
asked Nov 11 at 16:41
AdamK
72118
asked Nov 11 at 16:41
AdamK
72118
72118
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
up vote
1
down vote
accepted
If a problem A is NP-hard, then all NP problems are reducible to A in polynomial time.
Proof:
Since the problem A is not NP-Complete, then there exists problem B as defined above. All problems C in NP can be reduced to B in polynomial time, then B can be reduced to A in polynomial time. Composition of polynomial time algorithms is polynomial, so C can be reduced to A in polynomial time.
--
Since A is NP-Hard but not NP-Complete, A must not be in NP, therefore A is not in P either.
edited Nov 12 at 14:24
AdamK
72118
answered Nov 11 at 16:51
ralphmerridew
261
add a comment |
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
1
down vote
accepted
If a problem A is NP-hard, then all NP problems are reducible to A in polynomial time.
Proof:
Since the problem A is not NP-Complete, then there exists problem B as defined above. All problems C in NP can be reduced to B in polynomial time, then B can be reduced to A in polynomial time. Composition of polynomial time algorithms is polynomial, so C can be reduced to A in polynomial time.
--
Since A is NP-Hard but not NP-Complete, A must not be in NP, therefore A is not in P either.
edited Nov 12 at 14:24
AdamK
72118
answered Nov 11 at 16:51
ralphmerridew
261
add a comment |
up vote
1
down vote
accepted
If a problem A is NP-hard, then all NP problems are reducible to A in polynomial time.
Proof:
Since the problem A is not NP-Complete, then there exists problem B as defined above. All problems C in NP can be reduced to B in polynomial time, then B can be reduced to A in polynomial time. Composition of polynomial time algorithms is polynomial, so C can be reduced to A in polynomial time.
--
Since A is NP-Hard but not NP-Complete, A must not be in NP, therefore A is not in P either.
edited Nov 12 at 14:24
AdamK
72118
answered Nov 11 at 16:51
ralphmerridew
261
add a comment |
up vote
1
down vote
accepted
up vote
1
down vote
accepted
If a problem A is NP-hard, then all NP problems are reducible to A in polynomial time.
Proof:
Since the problem A is not NP-Complete, then there exists problem B as defined above. All problems C in NP can be reduced to B in polynomial time, then B can be reduced to A in polynomial time. Composition of polynomial time algorithms is polynomial, so C can be reduced to A in polynomial time.
--
Since A is NP-Hard but not NP-Complete, A must not be in NP, therefore A is not in P either.
edited Nov 12 at 14:24
AdamK
72118
answered Nov 11 at 16:51
ralphmerridew
261
If a problem A is NP-hard, then all NP problems are reducible to A in polynomial time.
Proof:
Since the problem A is not NP-Complete, then there exists problem B as defined above. All problems C in NP can be reduced to B in polynomial time, then B can be reduced to A in polynomial time. Composition of polynomial time algorithms is polynomial, so C can be reduced to A in polynomial time.
--
Since A is NP-Hard but not NP-Complete, A must not be in NP, therefore A is not in P either.
edited Nov 12 at 14:24
AdamK
72118
answered Nov 11 at 16:51
ralphmerridew
261
edited Nov 12 at 14:24
AdamK
72118
edited Nov 12 at 14:24
AdamK
72118
edited Nov 12 at 14:24
AdamK
72118
72118
answered Nov 11 at 16:51
ralphmerridew
261
answered Nov 11 at 16:51
ralphmerridew
261
answered Nov 11 at 16:51
ralphmerridew
261
261
add a comment |
add a comment |
Thanks for contributing an answer to Stack Overflow!
- 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.
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%2fstackoverflow.com%2fquestions%2f53250896%2fprove-a-problem-that-is-np-hard-and-not-np-complete-in-not-in-p%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
