3 ms·

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 knowledgeab

by Achshar 13y 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.

j2kun 13y 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-summer-holidays/ http://gowers.wordpress.com/2013/10/24/what-i-did-in-my-summ...
- codezero 13y ago
  This is an awesome summary, that I think I actually understand. Thanks!
- tzs 13y 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!"
  - j2kun 13y ago
    The open conjecture (officially, the existence of subexponentially strong pseudorandom function families), is a weaker variant of some stronger conjectures (the existence of polynomially-strong pseudorandom number generators) which actually imply P != NP. So in some sense the problems are very close to equivalent. But yes I think you're right, that nobody would take such an approach seriously.
cokernel 13y 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.2663&rep=rep1&type=pdf 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 http://en.wikipedia.org/wiki/Natural_proof). But I'd recommend reading Gowers's writing, which is much clearer.
tobiasSoftware 13y 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_multiplication_omega_over_time.svg 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.

by Achshar 13y 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.

j2kun 13y 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-summer-holidays/ http://gowers.wordpress.com/2013/10/24/what-i-did-in-my-summ...

codezero 13y ago
This is an awesome summary, that I think I actually understand. Thanks!
tzs 13y 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!"
- j2kun 13y ago
  The open conjecture (officially, the existence of subexponentially strong pseudorandom function families), is a weaker variant of some stronger conjectures (the existence of polynomially-strong pseudorandom number generators) which actually imply P != NP. So in some sense the problems are very close to equivalent. But yes I think you're right, that nobody would take such an approach seriously.

cokernel 13y 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.2663&rep=rep1&type=pdf 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 http://en.wikipedia.org/wiki/Natural_proof). But I'd recommend reading Gowers's writing, which is much clearer.

tobiasSoftware 13y 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_multiplication_omega_over_time.svg 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.