I'd side more with Scott than Lance and Bill in trading off our inability to prove lower bounds ('evidence' that P=NP) against our inability to find prove efficient algorithms for many NP problems ('evidence' that P!=NP). The efforts for algorithms have been much more extensive and have a much longer history than those for lower bounds but Lance and Bill seem to dismiss the comparative 'weight' of this evidence.

In some cases, our inability to prove lower bounds can actually be seen as 'evidence' of P!=NP: As Lance pointed out, we are currently unable to prove circuit lower bounds for some relatively weak classes of circuits. Our inability seems to be explained in part by the Razborov-Rudich Natural Proofs argument (e.g., see Lance's blog entry). This argument has no explanatory power if P=NP so the fact that we are stuck in finding lower bounds for these circuit models can then be viewed as 'evidence' for P!=NP.

(Maybe one could file this as a special case of the Self-Referential Argument, which is one of my favorites from Scott's list.)

The P vs. NP problem is only in its infancy. Thirty or forty years is not enough time in mathematical standards. In general we should not expect fast solutions to deep scientific problems.

I am surprised that Scott has not commented on this blog entry. Yo Scott---a blog post in your own weblog does not count. Post in the poster's territory, not the postee's territory :-)

Is it possible for a benevolent god to answer that prayer? That is to say, are there possible universes in which both "P = NP" and "humans exist" are true? I can imagine, like in some Ray Bradberry story, opening our eyes after that prayer has been answered only to discover we are now all cephalopods.

BTW, when is Bill going to be officially elevated from "guest" to "co-host"?

What is the track record for majority opinion with respect to hard cs theory problems?

ReplyDeleteI'd side more with Scott than Lance and Bill in trading off our inability to prove lower bounds ('evidence' that P=NP) against our inability to find prove efficient algorithms for many NP problems ('evidence' that P!=NP). The efforts for algorithms have been much more extensive and have a much longer history than those for lower bounds but Lance and Bill seem to dismiss the comparative 'weight' of this evidence.

ReplyDeleteIn some cases, our inability to prove lower bounds can actually be seen as 'evidence' of

P!=NP: As Lance pointed out, we are currently unable to prove circuit lower bounds for some relatively weak classes of circuits. Our inability seems to be explained in part by the Razborov-Rudich Natural Proofs argument (e.g., see Lance's blog entry). This argument has no explanatory power if P=NP so the fact that we are stuck in finding lower bounds for these circuit models can then be viewed as 'evidence' for P!=NP.

(Maybe one could file this as a special case of the Self-Referential Argument, which is one of my favorites from Scott's list.)

The P vs. NP problem is only in its infancy. Thirty or forty years is not enough time in mathematical standards. In general we should not expect fast solutions to deep scientific problems.

ReplyDeleteI am surprised that

ReplyDeleteScott has not commented on this blog entry. Yo Scott---a blog post in your own weblog does not count. Post in the poster's territory, not the postee's territory :-)Bill is christian, so he should not think that "god is evil". let's pray.

ReplyDeleteDear god,

please let P equal NP

amen

Is it possible for a benevolent god to answer that prayer? That is to say, are there possible universes in which both "P = NP" and "humans exist" are true? I can imagine, like in some Ray Bradberry story, opening our eyes after that prayer has been answered only to discover we are now all cephalopods.

ReplyDeleteBTW, when is Bill going to be officially elevated from "guest" to "co-host"?

Sorry, that should be Ray Brad

ReplyDeletebury.

ReplyDeleteI am surprised that Scott has not commented on this blog entry.Alrighty then...

Bill is christian, so he should not think that "god is evil".By that logic, Jews are almost theologically

obligatedto believe P!=NP.when israel was in Pessiland

ReplyDeleteO- pressed so hard they could not stand (waiting for their computations)

Go down Moses way down in Pessiland

tell old pharao (?)

let my people go (to Algorithmica)

*sorry*

>> Bill is christian, so he should not

ReplyDelete>> think that "god is evil".

> By that logic, Jews are almost

> theologically obligated to believe

> P!=NP.

A more accurate characterization of Judaism might be that God is subtle but not malicious.

=)

ReplyDeleteBill is christian, so he should not think that "god is evil".

By that logic, Jews are almost theologically obligated to believe P!=NP.

And I guess that Atheists are prone to believe that

P!=NP is independent of ZFC.Touche

ReplyDelete