Given a language A, which is in NP and also not NP-complete, I have to prove that P != NP.
[Note: A is not trivial]
Any suggestions?
Asked
Active
Viewed 70 times
1 Answers
1
If A is in NP but not NP-complete, that means it's not NP-hard. Now assume P = NP and show that every nontrivial language in NP is NP-hard under that assumption.
(The statement even holds for any nontrivial language at all.)
G. Bach
- 267
-
I stuck at this point, that's the reason I wrote this question. – Asaf Kahlon Jun 09 '14 at 17:10
-
If P = NP, what can you solve with the reduction you need for an NP-hardness proof? – G. Bach Jun 09 '14 at 17:11
-
realy have no idea... – Asaf Kahlon Jun 09 '14 at 17:40
-
What kind of algorithm is the reduction allowed to be? – G. Bach Jun 09 '14 at 17:44
-
Still don't get it – Asaf Kahlon Jun 09 '14 at 17:53
-
Maybe post what your understanding of NP-hardness is? – G. Bach Jun 09 '14 at 17:55
-
Language B is NP-hard if for all A in NP, there's a polinomial reduction from A to B – Asaf Kahlon Jun 09 '14 at 18:35
-
Alright, now if P = NP, what can your reduction from A to B solve for $A \in $ NP? – G. Bach Jun 09 '14 at 18:37
-
But we don't know that the reduction exists, since A is not NP-hard – Asaf Kahlon Jun 09 '14 at 19:18
-
1The comment should've been about $B,C \in$ NP to avoid confusion. Assume P = NP; can you then reduce $B$ to $C$ in deterministic polynomial time? How? – G. Bach Jun 09 '14 at 19:22
-
How can I do such reduction? – Asaf Kahlon Jun 09 '14 at 19:29
-
I realy don't understand what you're trying to tell me. Can you please give me a better hint? (or solution because It's the first time I try to solve such question). – Asaf Kahlon Jun 09 '14 at 19:46
-
I could, but that's not the purpose of exercise; since this is homework, I expect you will be told the solution in due time, so not getting an answer now shouldn't deprive you of getting a solution at all. When I get stuck, I usually lean back, forget about it for today, mull it over and try again tomorrow. – G. Bach Jun 09 '14 at 19:51
-
I understand you, but I think that there's something I'm missing here, and if I see a given proof now, I'll be able to solve by myself in future homeworks. – Asaf Kahlon Jun 09 '14 at 20:01