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 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 :-)
ReplyDeleteBill 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 Bradbury.
ReplyDeletewhen 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.
=)
Bill is christian, so he should not think that "god is evil".
ReplyDeleteBy 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.