How not to prove that P is not equal to NP

http://gowers.wordpress.com/2013/10/03/how-not-to-prove-that-p-is-not-equal-to-np

by dominotw • 13 years ago

34 14 13 years ago

gowers.wordpress.com

Achshar• 13 years ago

Can any one explain the article? It looks too technical for me and I am not good with advanced maths. I have an idea of what p != NP is but not very knowledgeable about it.

j2kun2• 13 years ago

In the quest to prove P != NP a great number of techniques have been tried, and many of these techniques have attempted to use circuit complexity. The circuit complexity of a function with n inputs is, roughly, the size of the smallest circuit that computes it. This is a function depending on n, and so we can talk about polynomial size circuits, etc. The important fact is that if we can find a specific problem (a problem in NP) which doesn't have a polynomial size circuit, then P is not NP.

Unfortunately many of the elementary techniques that try to show this don't work, and for a long time nobody knew why. Then in the 90's Alexander Razborov and Steven Rudich proved a general theorem that these elementary techniques could never prove P != NP.

What Gowers explains in his blog post (and the follow-up) is the Razborov-Rudich theorem, called natural proofs. Roughly, it says that all of the attempted techniques use a "natural" property P of boolean functions. A natural property P asserts one specific function needs large circuits, while all small circuits cannot satisfy the property (and P is efficiently computable, in a sense).

The insight is that all of these properties also apply to TOO MANY other functions. Indeed, if P is natural for polynomial size circuits, and it applies to too many functions, then it can be used to violate another well known conjecture in cryptography, a conjecture on the existence of a certain kind of secure pseudorandom number generator. This is the heart of R-R's theorem, and it's quite a beautiful proof.

Nowadays there are three known "barriers" to proving P is not NP, and any proposed method for solving the problem first needs to argue that it bypasses all of these barriers. The first is called relativization (having to do with oracles), the second naturalization (this natural proofs barrier), and the third algebrization (which I'm not familiar with).

Tim Gower's is actually using this post as a platform to propose a new method for separating P from NP, and so he's studying these barriers to argue why his method bypasses them. For more on his new proposal, see: http://gowers.wordpress.com/2013/10/24/what-i-did-in-my-summ...

codezero• 13 years ago

This is an awesome summary, that I think I actually understand. Thanks!

tzs• 13 years ago

Indeed, if P is natural for polynomial size circuits, and it applies to too many functions, then it can be used to violate another well known conjecture in cryptography, a conjecture on the existence of a certain kind of secure pseudorandom number generator

Has this completely stopped the search for a natural proof that P!=NP, or are there (real--not crackpot) researchers who now simply think "Cool...now I've got a shot at both proving that P!=NP and disproving a widely believed conjecture that is vital to modern cryptography! That gets me tenure and a Field's medal for sure!"

cokernel• 13 years ago

The two blog posts by Gowers are attempting to provide an exposition of the Razborov--Rudich paper "Natural Proofs" (http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.41....).

One way to try to prove that P != NP is to identify some "natural combinatorial property" that problems in P have that problems in NP do not share. The problem (as Gowers explains) is that any such property is either incredibly complicated or actually applies to almost any random problem in NP. Razborov and Rudich state and prove a technical version of this statment, which implies that attempting to use "natural combinatorial properties" to prove P != NP is a non-starter. (Hence the title of Gowers's blog post.)

For another summary, you might look at the relevant article on Wikipedia (http://en.wikipedia.org/wiki/Natural_proof). But I'd recommend reading Gowers's writing, which is much clearer.

tobiasSoftware• 13 years ago

I can't explain the article but I can explain P vs NP (it's been a few years though so please forgive any mistakes). P and NP are two classes of problems. P is simply problems with an input n that can be solved in n^c time for some value of c. So sorting n items is in class P, because it's bounded by n log n, (which will be smaller than n^2 for example).

NP is a harder concept to grasp, the N actually stands for Non-deterministic. My college teacher explained it like this: imagine you could send out as many clones as you wanted to, and if any clone solves the problem, then the problem is solved. The way this gets explained a lot is that NP is the class of problems that can be verified in Polynomial time.

One place NP really matters is security. Think of a password, a longer password makes it exponentially harder to brute force, but it's only linearly longer to check. If P=NP, then this would mean certain password type problems could be cracked in polynomial time. Now this might still be a large polynomial, maybe it would be n^1029281, but this would still excite scientists, partly because once something is polynomial time it opens the door to get exponent smaller. One example of this is matrix multiplication, where the exponent has gone from 3 to under 2.4 over the years (http://en.wikipedia.org/wiki/File:Bound_on_matrix_multiplica...).

Note that some of these problems that have to do with security have been thoroughly studied and no one believes there is an "easy" (polynomial) way to crack these types of security, which implies P != NP, we just can't completely prove it.

Another interesting thing is that if any problem in the NP "complete" class of problems can be solved in Polynomial time, there are ways to map the problems between each other and thus all of them could be solved in Polynomial time. The "core" problem I've seen listed is the Boolean Satisfiability problem, given a boolean formula with n clauses, can you find variables to satisfy those clauses. All NP complete problems are variations of this problem, essentially different phrasings of it.

jackmaney2• 13 years ago

Wow, a double negative! Does this mean that the article shows how to prove that P is equal to NP? :P

foldr• 13 years ago

No, because the the two negatives don't cancel out in this case. "I didn't prove that 3 isn't prime" doesn't mean the same thing as "I proved that 3 is prime" (because one negation is in the matrix clause and the other is in the embedded clause).

jackmaney2• 13 years ago

Yes, hence the emoticon.

StavrosK• 13 years ago

Ugh, I don't see what all the fuss is about. Here, let me do you all a favor:

P = NP

P/P = NP/P

N = 1

Which is absurd, because N is a letter. Therefore, P != NP.

You're welcome.

11001• 13 years ago

Alternative proof:

Suppose, P = NP

P² = P(NP)

(subtracting (NP)²)

P² - (NP)² = P(NP) - (NP)²

(dividing both sides by P-(NP)):

P + (NP) =(NP)

since P = NP (initial assumption):

2*P = P

(dividing by P):

2 = 1

which is a contradiction, therefore P \not= NP

hausen• 13 years ago

Gaaah! My eyes! You assumed that P = NP, therefore you cannot divide by P - NP = P - P = 0.

I think that mistake shows that even finding a mock proof for the fact that P != NP is hard.

How not to prove that P is not equal to NP

Related Stories