Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
NCTM or The Math Forum.



Re: an interesting observation about Natural Proofs
Posted:
Nov 10, 2011 11:29 AM


On Nov 9, 11:58 am, Craig Feinstein <cafei...@msn.com> wrote: > Unless it is an axiom that P!=NP, any proof of P!=NP has to be > essentially be of the form: > > f solves SAT > f in C > f in C > f cannot be computed in polynomial time. > Therefore, f solves SAT > f cannot be computed in polynomial time. > > The RazborovRudich paper on "Natural Proofs" essentially shows that > if (1) C is a property that is common (Largeness) and (2) it is easy > to check whether a function f has property C (Constructivity or Low > Complexity), then the above proof cannot be valid unless "pigs can > fly". > > Suppose C is an uncommon property, so (1) is broken. In the most > extreme case, C=the class of functions which solve SAT. Then the above > proof would be of the form: > > f solves SAT > f solves SAT > f solves SAT > f cannot be computed in polynomial time. > Therefore, f solves SAT > f cannot be computed in polynomial time. > > So this proof would be of the form "P!=NP because P!=NP". > > Now, suppose it is difficult to check whether a function f has > property C, so (2) is broken. In the most extreme case, C = the class > of functions f that cannot be computed in polynomialtime. Then the > above proof would be of the form: > > f solves SAT > f cannot be computed in polynomial time > f cannot be computed in polynomial time > f cannot be computed in > polynomial time. > Therefore, f solves SAT > f cannot be computed in polynomial time. > > So this proof would be of the form "P!=NP because P!=NP". > > So we see that breaking one of the two conditions for a natural proof, > largeness or constructivity, leads one in the direction of a proof of > the flavor "P!=NP because P!=NP". And the two conditions, largeness > and constructivity, are "natural" because they lead a proof away from > a proof of the flavor "P!=NP because P!=NP". From this observation, we > can conclude that a proof that P!=NP cannot involve deep mathematics, > since deep mathematics is "natural", at least "natural" to > mathematicians. For example, here is one such proof: > > SUBSETSUM (where the target integer is zero) is equivalent to the > problem of determining whether the set of subsetsums of {s1,...,sk} > and the set of subsetsums of {s_{k+1},...,s_n} intersect > nontrivially. There are 2^k members of the set of subsetsums of > {s1,...,sk} and 2^{nk} members of the set of subsetsums of {s_{k > +1},...,s_n}, and it is impossible to simplify the problem further. > > Hence, since the combined size of the sets that the SUBSETSUM problem > is about is 2^k+2^{nk}, for k in {1,...,n}, we can get a lower bound > for the worstcase runningtime of an algorithm that solves SUBSETSUM > by minimizing 2^k+2^{nk}, s.t. k in {1,...,n}. We get 2^{n/2}, so > Omega(2^{n/2}) is an exponential lower bound for algorithms which > solve SUBSETSUM. > > This is an example of a "supernatural proof". It is not natural, > because in this case, C=the set of functions that cannot be computed > in o(2^{n/2}) time, so it violates the constructivity property above. > And it also does not involve deep mathematics. This supernatural proof > is almost of the form "P!=NP because P!=NP", but not quite or else it > would be a circular argument. > > I believe that the reason why the P vs NP problem has been considered > so difficult is because of human psychology. Most people either want > there to be some deep reason why P!=NP (some almost magic secret using > some deep mathematics like the proof of FLT had) or they refuse to > believe that P!=NP. They don't want to accept that there is no deep > reason why P!=NP. It essentially just is.
Not everything I said in this post is technically correct. But I think the idea is correct.



