Complexity: When P not equal NP

Page 1 of 1

8 Replies - 1068 Views - Last Post: 08 August 2016 - 09:01 AM

#1 harro.rm

Reputation: 0
• Posts: 63
• Joined: 18-June 16

Complexity: When P not equal NP

Posted 06 August 2016 - 03:30 PM

I was wondering if someone can explain the truth statement of these two:

1. If P /= NP, then no problem in NP can be solved in poly time.
2. If P /= NP, then no problem in NP-complete can be solved in poly time.

Would #1 be false because P is still within domain of NP? As for #2, I'm not too sure but leaning towards true.
Is This A Good Question/Topic? 0

Replies To: Complexity: When P not equal NP

#2 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 12324
• Posts: 45,424
• Joined: 27-December 08

Re: Complexity: When P not equal NP

Posted 06 August 2016 - 03:34 PM

You are correct on #1. Now if P != NP, then what happens if an NP-Complete problem can be solved in polynomial time? Would it be in P? What does that imply?

#3 harro.rm

Reputation: 0
• Posts: 63
• Joined: 18-June 16

Re: Complexity: When P not equal NP

Posted 06 August 2016 - 05:00 PM

So the reason I thought it was true, was because if a problem is NP-complete, then it must be NP-hard and NP. Which would imply that P=NP? So a contradiction, is that correct?

#4 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 12324
• Posts: 45,424
• Joined: 27-December 08

Re: Complexity: When P not equal NP

Posted 06 August 2016 - 05:15 PM

An NP-Complete problem is both in NP (note that NP is a set, so you should say that the problem is in NP rather than that the problem is NP) and NP-Hard. This is the definition of NP-Completeness. So why can we deduce that P = NP? Try to fill in the details based on my hints in my last post.

#5 harro.rm

Reputation: 0
• Posts: 63
• Joined: 18-June 16

Re: Complexity: When P not equal NP

Posted 06 August 2016 - 06:41 PM

If an NP-complete problem can be solved in poly time, and P != NP, then that means there is a problem X that is in NP and in P? Since P = NP means is there a problem X in NP but not in P. But P != NP hasn't been proven yet.

So statement is false, because no one has been able to prove that P != NP?

#6 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 12324
• Posts: 45,424
• Joined: 27-December 08

Re: Complexity: When P not equal NP

Posted 06 August 2016 - 06:46 PM

Quote

If an NP-complete problem can be solved in poly time, and P != NP, then that means there is a problem X that is in NP and in P?

But P is a subset of NP.

Quote

Since P = NP means is there a problem X in NP but not in P.

I think you mean if P != NP, then there is a problem X in NP but not in P. This is a non-trivial result known as Ladner's Theorem. Don't claim this, unless you either offer a proof or your instructor has proven this for you all.

Quote

So statement is false, because no one has been able to prove that P != NP?

No.

The statement you are trying to prove is equivalent to the following statement: If an NP-Complete problem X is in P, then P = NP.

It is clear that if an NP-Complete problem has a polynomial time solution, it is in P. So now use the solution for the NP-Complete problem to construct a polynomial time solution for every problem in NP. Your definition of NP-Hard will be useful here.

#7 harro.rm

Reputation: 0
• Posts: 63
• Joined: 18-June 16

Re: Complexity: When P not equal NP

Posted 06 August 2016 - 06:59 PM

Argh, I guess I'm just confused with the definition of P=NP and P!=NP.

#8 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 12324
• Posts: 45,424
• Joined: 27-December 08

Re: Complexity: When P not equal NP

Posted 06 August 2016 - 07:04 PM

P is the set of languages L which are decidable in polynomial time. NP is the set of languages L in which a string w \in L can be verified to be in L by a Turing Machine in polynomial time. There are slightly more exact definitions of each, but I suspect you're in an algorithms class rather than a theory of computation class. So these definitions will suffice.

So P = NP and P != NP refer to whether or not the two sets are equal.

#9 mojo666

Reputation: 408
• Posts: 882
• Joined: 27-June 09

Re: Complexity: When P not equal NP

Posted 08 August 2016 - 09:01 AM

It may help to draw a ven diagram representing the current state of things. Draw a large circle on a piece of paper. This circle is NP. Draw two smaller circles within the large one that do not overlap each other. One of these circles is P and the other is NP-complete. With our current knowledge this is the apparent state of the problem (though not proven). There are problems in P (which are also NP). There are problems in NPComplete(which are also NP but don't appear to be P). There are also NP problems that are neither in P nor shown to be NPComplete. NPComplete problems are all equivalent, so if one was shown to be P, then all of them would be P. Thus we would erase the NPComplete circle and draw it inside the P circle. This would have no effect on the other NP problems.