tag:blogger.com,1999:blog-3722233.post116111702097060121..comments2024-03-27T19:58:17.387-05:00Comments on Computational Complexity: Scott and P versus NPLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger10125tag:blogger.com,1999:blog-3722233.post-1161206076571557192006-10-18T16:14:00.000-05:002006-10-18T16:14:00.000-05:00Bill is christian, so he should not think that "go...<I>Bill is christian, so he should not think that "god is evil".<BR/><BR/>By that logic, Jews are almost theologically obligated to believe P!=NP.</I><BR/><BR/><BR/><BR/>And I guess that Atheists are prone to believe that <B> P!=NP is independent of ZFC</B>.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1161205301424232572006-10-18T16:01:00.000-05:002006-10-18T16:01:00.000-05:00>> Bill is christian, so he should not >> think th...>> Bill is christian, so he should not <BR/>>> think that "god is evil".<BR/><BR/>> By that logic, Jews are almost <BR/>> theologically obligated to believe <BR/>> P!=NP.<BR/><BR/>A more accurate characterization of Judaism might be that God is subtle but not malicious. <BR/><BR/>=)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1161196122620568332006-10-18T13:28:00.000-05:002006-10-18T13:28:00.000-05:00when israel was in PessilandO- pressed so hard the...when israel was in Pessiland<BR/><BR/>O- pressed so hard they could not stand (waiting for their computations)<BR/><BR/>Go down Moses way down in Pessiland<BR/><BR/>tell old pharao (?)<BR/><BR/>let my people go (to Algorithmica)<BR/><BR/>*sorry*Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1161192920619130092006-10-18T12:35:00.000-05:002006-10-18T12:35:00.000-05:00Sorry, that should be Ray Bradbury.Sorry, that should be Ray Brad<EM>bury</EM>.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1161192194937248392006-10-18T12:23:00.000-05:002006-10-18T12:23:00.000-05:00Is it possible for a benevolent god to answer that...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.<BR/><BR/>BTW, when is Bill going to be officially elevated from "guest" to "co-host"?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1161189713132544572006-10-18T11:41:00.000-05:002006-10-18T11:41:00.000-05:00Bill is christian, so he should not think that "g...Bill is christian, so he should not think that "god is evil". let's pray.<BR/><BR/>Dear god,<BR/>please let P equal NP<BR/>amenAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1161184516533802372006-10-18T10:15:00.000-05:002006-10-18T10:15:00.000-05:00I am surprised that Scott has not commented on thi...I am surprised that <B>Scott has not commented on this blog entry</B>. Yo Scott---a blog post <A HREF="http://www.scottaaronson.com/blog/" REL="nofollow">in your own weblog</A> does not count. Post in the poster's territory, not the postee's territory :-)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1161169863639213722006-10-18T06:11:00.000-05:002006-10-18T06:11:00.000-05:00The P vs. NP problem is only in its infancy. Thirt...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.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1161156464851013882006-10-18T02:27:00.000-05:002006-10-18T02:27:00.000-05:00I'd side more with Scott than Lance and Bill in tr...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. <BR/><BR/>In some cases, our inability to prove lower bounds can actually be seen as 'evidence' of <BR/>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 <A HREF="http://weblog.fortnow.com/2006/05/importance-of-natural-proofs.html" REL="nofollow">blog entry</A>). 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.<BR/><BR/>(Maybe one could file this as a special case of the Self-Referential Argument, which is one of my favorites from Scott's list.)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1161149155463138752006-10-18T00:25:00.000-05:002006-10-18T00:25:00.000-05:00What is the track record for majority opinion with...What is the track record for majority opinion with respect to hard cs theory problems?Anonymousnoreply@blogger.com