# P versues. NP

• May 17th 2006, 06:58 PM
ThePerfectHacker
P versues. NP
As I understand this is an open and unsolved problem in math. I just wanted to ask what is it? Keep it simple never learned this stuff. Also if you may explain what computational complexity theory is. I tried wiki but could not understand.
• May 18th 2006, 10:20 PM
rgep
The question is about decision problems. We are looking for algorithms which determine whether a binary string S has a certain property Q. By using the idea of encoding a number, graph, function or whatever onto a binary string, we can speak more generally of deciding whether some mathematical object has a certain property. For example, "does S represent a prime number", "does S represent a composite number", "does S encode a graph which is connected", "does S encode a graph which has a Hamiltonian cycle", "does S encode a boolean function which is ever true". So the decision problem associated to Q is that of deciding whether the input represents an object with property Q.

An important point which I'll mention here. The algorithm is only required to give the answer Yes when the input string does indeed have the property. If the input does not the algorithm may or may not terminate (but if it does, it musgive the correct answer of course!).

A property, or decision problem, Q is in the class P (polynomial) if there exists an algorithm A which detects that S has property Q and which runs in time n^c where n is the length of the input string and c is a fixed constant depending only on A (this is "polynomial time"). It's an exercise in graph theory to show that if we encode a graph on V vertices by its V-by-V adjacency matrix, and then write that out as a list of length n=V^2, it is possible to check that the graph is connected in V matrix multiplications, ie V^4 operations. So this property is in class P. More recently it was shown that deciding whether a number is prime is in class P.

A property Q is in class NP (non-deterministic polynomial) is there is an algorithm which can determine that S has property Q given some auxiliary input (which you could think of as a certificate, or witness, of S having that property). The algorithm is not required to produce that certificate, merely to check it. It should then run in time n^C as before. So, for example, if Q is "S represents a composite number" then an algorithm that takes as its certificate a factor and checks that is does indeed divide the input, runs in polynomial time. Similarly, for "does S encode a graph which has a Hamiltonian cycle", where the certificate is the path itself.

The question "does S encode a boolean function which is ever true" is in NP (the certificate being an assignment of values to the variables making it true". The property, SAT, is NP-complete. Every problem in NP can be encoded in terms of a Boolean formula and the certificate in terms of an assignment of values to the variables.

The big problem is about the relation between the classes P and NP. Clearly every problem in P is automatically in NP (with a null certificate). Is P = NP? Since SAT is NP-complete, a polynomial time algorithm for solving SAT without a certificate (ie a polynomial time for finding rather than merely checking the solution) would be enough to show that P = NP.
• May 19th 2006, 04:34 AM
CaptainBlack
Quote:

Originally Posted by rgep
The question is about decision problems.
:
:

I think I would have pitched this at a slightly more elementary level
myself .

RonL
• May 19th 2006, 09:14 AM
rgep
Quote:

I think I would have pitched this at a slightly more elementary level
Feel free to do so ...
• May 19th 2006, 09:50 AM
ThePerfectHacker
Thank you rgep (though not fully understood), why is it so important?

Can P=NP be independent?
• May 19th 2006, 10:39 PM
rgep
There are some good resources at the Clay Mathematics Institute site.
• May 19th 2006, 11:13 PM
CaptainBlack
Quote:

Originally Posted by rgep
Feel free to do so ...

Roger Penrose already has in "The Emperor's New Mind", pages 181-187.

It's a bit too long to reproduce here, but it is pitched at the right level
for someone not familiar with the field.

Or chapter 6 of David Harel's "Algorithmics"

RonL