```Date: Nov 9, 2011 11:58 AM
Author: Craig Feinstein
Subject: an interesting observation about Natural Proofs

Unless it is an axiom that P!=NP, any proof of P!=NP has to beessentially be of the form:f solves SAT -> f in Cf in C -> f cannot be computed in polynomial time.Therefore, f solves SAT -> f cannot be computed in polynomial time.The Razborov-Rudich paper on "Natural Proofs" essentially shows thatif (1) C is a property that is common (Largeness) and (2) it is easyto check whether a function f has property C (Constructivity or LowComplexity), then the above proof cannot be valid unless "pigs canfly".Suppose C is an uncommon property, so (1) is broken. In the mostextreme case, C=the class of functions which solve SAT. Then the aboveproof would be of the form:f solves SAT -> f solves SATf 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 hasproperty C, so (2) is broken. In the most extreme case, C = the classof functions f that cannot be computed in polynomial-time. Then theabove proof would be of the form:f solves SAT -> f cannot be computed in polynomial timef cannot be computed in polynomial time -> f cannot be computed inpolynomial 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 ofthe flavor "P!=NP because P!=NP". And the two conditions, largenessand constructivity, are "natural" because they lead a proof away froma proof of the flavor "P!=NP because P!=NP". From this observation, wecan conclude that a proof that P!=NP cannot involve deep mathematics,since deep mathematics is "natural", at least "natural" tomathematicians. For example, here is one such proof:SUBSET-SUM (where the target integer is zero) is equivalent to theproblem of determining whether the set of subset-sums of {s1,...,sk}and the set of subset-sums of {-s_{k+1},...,-s_n} intersectnontrivially. There are 2^k members of the set of subset-sums of{s1,...,sk} and 2^{n-k} members of the set of subset-sums 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 SUBSET-SUM problemis about is 2^k+2^{n-k}, for k in {1,...,n}, we can get a lower boundfor the worst-case running-time of an algorithm that solves SUBSET-SUMby minimizing 2^k+2^{n-k}, s.t. k in {1,...,n}. We get 2^{n/2}, soOmega(2^{n/2}) is an exponential lower bound for algorithms whichsolve SUBSET-SUM.This is an example of a "supernatural proof". It is not natural,because in this case, C=the set of functions that cannot be computedin o(2^{n/2}) time, so it violates the constructivity property above.And it also does not involve deep mathematics. This supernatural proofis almost of the form "P!=NP because P!=NP", but not quite or else itwould be a circular argument.I believe that the reason why the P vs NP problem has been consideredso difficult is because of human psychology. Most people either wantthere to be some deep reason why P!=NP (some almost magic secret usingsome deep mathematics like the proof of FLT had) or they refuse tobelieve that P!=NP. They don't want to accept that there is no deepreason why P!=NP. It essentially just is.
```