tag:blogger.com,1999:blog-3722233.post214044932002357227..comments2021-01-23T11:48:16.046-06:00Comments on Computational Complexity: Lets Prove Something instead of proving that we can't prove somethingLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger12125tag:blogger.com,1999:blog-3722233.post-58622198336799024882010-04-06T10:10:21.450-05:002010-04-06T10:10:21.450-05:00Dear past and future commenters:
note the date tha...Dear past and future commenters:<br />note the date that this post was made.<br /><br />bill gasarchGASARCHnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-26221385633426355612010-04-05T14:14:54.248-05:002010-04-05T14:14:54.248-05:00A general comment, the unprovability results like ...A general comment, the unprovability results like BGS and RR were by people who were trying to solve the problems. In rephrasing what Sasha said in the first barriers workshop, the natural proof barrier was intended to guide people in proving lower bounds and how to solve the open problems.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-73575907184241802712010-04-05T14:07:42.682-05:002010-04-05T14:07:42.682-05:00For 4.1,
I think they are equal. NPR is an existe...For 4.1,<br /><br />I think they are equal. NPR is an existential quantifier bounded by a PR in front of a PR predicate. Since you can do PR bounded search in PR, you can compute it in PR.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-30028620919439917322010-04-02T05:33:06.711-05:002010-04-02T05:33:06.711-05:00While on the subject of invigorating the field, wh...While on the subject of invigorating the field, what are your thoughts on the future of theoretical computer science? Are you seeing an increase or decrease in undergraduates interested in theoretical computer science? An increase or decrease in graduate school applications to your departments? Do you feel that attitudes towards funding for theory are getting more positive or more negative from within your faculty, and from funding agencies? Are people from other disciplines more or less aware of theory than they were in the past? What countries do you think will emerge as theory hot spots in the future? ect ect... It would be great if a wide range of theorists could share their observations.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-87877404524160448552010-04-01T19:09:56.895-05:002010-04-01T19:09:56.895-05:00Hmmmm ... it seems to me that GASARCH's point-...Hmmmm ... it seems to me that GASARCH's point-of-view can invigorate pretty much any discipline ... for example ...<br /><br />-------------------<br /><br />We complexity(<i>quantum</i>) theorists seem more concerned with proving that we can't prove (<i>simulate</i>) things than with actually proving (<i>simulating</i>) things !!!!<br /><br />We are in a rut. We seem to have the urge to show a theorem (<i>system</i>) is hard to prove (<i>simulate</i>) rather than to actually prove (<i>simulate</i>) it! <br /><br />To be fair, many of our conjectures (<i>quantum models</i>) are hard to prove (<i>simulate</i>). Even so, we need to get out of this rut.John Sidleshttp://www.mrfm.orgnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-73943823371991688952010-04-01T16:22:27.402-05:002010-04-01T16:22:27.402-05:00Oh for proper containment you need the space hiera...Oh for proper containment you need the space hierarchy theorem too I guess.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-50131739772307053512010-04-01T16:20:23.722-05:002010-04-01T16:20:23.722-05:00Um, isn't NL contained in PSPACE immediate fro...Um, isn't NL contained in PSPACE immediate from Savitch's Theorem?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-39990169861220939272010-04-01T12:34:11.976-05:002010-04-01T12:34:11.976-05:00I prove that NP is not equal to DTIME(2^{O(n)} bel...I prove that NP is not equal to DTIME(2^{O(n)} below:<br /><br />NP is closed under polynomial time m-one-reductions.<br />On the other hand, DTIME(2^{O(n)}<br />is not closed under polynomial time m-one reductions.<br /><br />Therefore, NP is not equal to <br />DTIME(2^{O(n)}).<br /><br />One of major open problems in complexity<br />is to separate NP from EXP=DTIME(2^{n^{O(1)}).<br /><br />BinAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-42635979738979532952010-04-01T11:20:26.390-05:002010-04-01T11:20:26.390-05:00Well, if EXP = DTIME(2^O(n)), anything is true...Well, if EXP = DTIME(2^O(n)), anything is true...Rahulnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-13986169200304401782010-04-01T11:08:47.216-05:002010-04-01T11:08:47.216-05:00It's a testament to Bill's "style&quo...It's a testament to Bill's "style" that it is (NP-)hard to distinguish between Bill's real posts and his april fool's day posts ..Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-34803000227648816032010-04-01T11:03:06.434-05:002010-04-01T11:03:06.434-05:00I think 4.2 should be numbered 4.1 because that...I think 4.2 should be numbered 4.1 because that's what it is :P. Happy April Fool's Day!Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-14591483165743358482010-04-01T09:41:56.737-05:002010-04-01T09:41:56.737-05:00Isn't 4.2 known? DFAs with 2^q states can simu...Isn't 4.2 known? DFAs with 2^q states can simulate NFA's with q states. I think this simulation is known to be tight.<br /><br />What did you mean in 4.2?<br /><br />adamAnonymousnoreply@blogger.com