This work is licensed under a
Creative Commons License.
|
Tuesday, October 17, 2006
Scott and P versus NP
Posted by Lance
In the eighth Complexitycast, Bill Gasarch and I dissect Scott Aaronson's Ten Arguments for Believing P≠NP and briefly Bill's P versus NP Poll. MP3 (24:55, 4.3MB)3:29 PM #
-
What is the track record for majority opinion with respect to hard cs theory problems?
-
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 :-)
-
Bill is christian, so he should not think that "god is evil". let's pray.
Dear 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.
BTW, when is Bill going to be officially elevated from "guest" to "co-host"?
-
Sorry, that should be Ray Bradbury.
-
I 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 obligated to believe P!=NP.
-
when israel was in Pessiland
O- 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
>> 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".
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
Links to this post:
Weblog Home
Archives
