Date: Nov 10, 2011 11:29 AM Author: Craig Feinstein Subject: Re: an interesting observation about Natural Proofs 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 Razborov-Rudich 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 polynomial-time. 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:

>

> SUBSET-SUM (where the target integer is zero) is equivalent to the

> problem of determining whether the set of subset-sums of {s1,...,sk}

> and the set of subset-sums of {-s_{k+1},...,-s_n} intersect

> nontrivially. 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 problem

> is about is 2^k+2^{n-k}, for k in {1,...,n}, we can get a lower bound

> for the worst-case running-time of an algorithm that solves SUBSET-SUM

> by minimizing 2^k+2^{n-k}, 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 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 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.