Drexel dragonThe Math ForumDonate to the Math Forum



Search All of the Math Forum:

Views expressed in these public forums are not endorsed by Drexel University or The Math Forum.


Math Forum » Discussions » sci.math.* » sci.math

Topic: an interesting observation about Natural Proofs
Replies: 1   Last Post: Nov 10, 2011 11:29 AM

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]
Craig Feinstein

Posts: 398
Registered: 12/13/04
an interesting observation about Natural Proofs
Posted: Nov 9, 2011 11:58 AM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

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.



Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© Drexel University 1994-2014. All Rights Reserved.
The Math Forum is a research and educational enterprise of the Drexel University School of Education.