tag:blogger.com,1999:blog-3722233.post5940936868926407886..comments2024-03-28T18:17:00.135-05:00Comments on Computational Complexity: We Still Can't Beat RelativizationLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger6125tag:blogger.com,1999:blog-3722233.post-79417044141875321342016-06-03T04:54:54.018-05:002016-06-03T04:54:54.018-05:00ll the known confirmation systems at the time rela...ll the known confirmation systems at the time relativized, i.e., in the event that you demonstrated two classes were the same or distinctive, they would be the same of various in respect to any set. BGS suggested that these strategies couldn't settle the P v NP issue.<a href="http://federalresumewritingservice.net/" rel="nofollow">click here</a>Anonymoushttps://www.blogger.com/profile/00040149432315527017noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-9009430396285449702016-01-31T05:59:37.778-06:002016-01-31T05:59:37.778-06:00A sentence like "we created relativized world...A sentence like "we created relativized worlds that make nearly all the open questions of complexity classes between P and PSPACE both true and false" makes me wonder why we focused on extremely powerful classes like PSPACE here. Why not create relativized worlds to make all open question between L-uniform NC^1 and NP both true and false? Or between ALogTime and PH, if we want to think big? And why only focus on relativization, and not also try to carry over the natural proofs and the algebrizing proofs barrier (to L != PH for example)?Jakitohttps://www.blogger.com/profile/08235089048981338795noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-73018586998196433812016-01-28T20:57:10.416-06:002016-01-28T20:57:10.416-06:00Do we know any barriers to the method used by Ryan...Do we know any barriers to the method used by Ryan in his ACC vs. NEXP result? <br /><br />His result actually made me hopeful that he might make considerable progress in settling questions at least about small complexity classes. My limited understanding was that we just need to find good representations of small circuit classes and then exploit it to give faster algorithms for them. This should push people to look for representation theorems for small classes. Unfortunately it seems that the only person who is really pushing this thread is Ryan.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-84796096272119758472016-01-28T18:40:53.662-06:002016-01-28T18:40:53.662-06:00Indeed, NEXP not in ACC doesn't relativize. In...Indeed, NEXP not in ACC doesn't relativize. In particular, all known SAT algorithms that beat exhaustive search are non-relativizing. ryanwhttps://www.blogger.com/profile/09644595632189419277noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-53720727787066371192016-01-28T12:05:06.638-06:002016-01-28T12:05:06.638-06:00I thought the whole point of the Aaronson, Wigders...I thought the whole point of the Aaronson, Wigderson paper you linked to on algebrization is that we CAN get past relativization (via arithmetization) but that it's not good enough and so they introduce their new barrier<br />A lot of the circuit lower bounds of the last decade got past, I thought, both naturalization (via diagonalization) and relativization (via arithmetization) simultaneously by combining the two techniques<br /><br />So, don't we have good wways to get past relativization? And then Aaronson and Wigderson's response was that Yes, we get past it, but here's a new barrier (algebrization) that all our techniques to go past it succumb toAnonymoushttps://www.blogger.com/profile/05260705122889615843noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-35337687840225184452016-01-28T07:39:57.361-06:002016-01-28T07:39:57.361-06:00I thought Ryan Williams lower bound did not relati...I thought Ryan Williams lower bound did not relativize.<br />GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.com