tag:blogger.com,1999:blog-3722233.post113227920797776998..comments2019-10-21T21:47:16.813-04:00Comments on Computational Complexity: Relativized Collapse of P and NPLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger6125tag:blogger.com,1999:blog-3722233.post-1132620809884123812005-11-21T19:53:00.000-05:002005-11-21T19:53:00.000-05:00"BTW, what is H?"H = Halting set."BTW, what is H?"<BR/><BR/>H = Halting set.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1132565483923826642005-11-21T04:31:00.000-05:002005-11-21T04:31:00.000-05:00"some subtleties with the definition of space-boun..."some subtleties with the definition of space-bounded oracle machines" seems to be the following:<BR/><BR/>For *nondeterministic* space-bounded oracle machines, during the period of writing down the query word on query tape, we don't allow any nondeterministic move.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1132525353652350202005-11-20T17:22:00.000-05:002005-11-20T17:22:00.000-05:00(Oops --- I take that back!)(Oops --- I take that back!)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1132525260909937182005-11-20T17:21:00.000-05:002005-11-20T17:21:00.000-05:00Since for all we know P = PSPACE it is not clear t...Since for all we know P = PSPACE it is not clear that any such oracle exists (though there may be some subtleties with the definition of space-bounded oracle machines that I am missing)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1132516731247270242005-11-20T14:58:00.000-05:002005-11-20T14:58:00.000-05:00Lance, this post seems to suggest that if an oracl...Lance, this post seems to suggest that if an oracle A is powerful "enough", then P^A captures PSPACE^A. For instance, we can go up in resources for A, like setting A = EEXPTIME... (but it doesn't directly suggest that the halting oracle works.)<BR/><BR/>I also understand that if A is "just" NP, then we need a collapse in the PH for the capture.<BR/><BR/>My question is: precisely what is the least powerful oracle B that we know for sure that P^B does not capture PSPACE^B?<BR/><BR/>Or perhaps this is not a monotone property at all?<BR/><BR/>BTW, what is H? Thanks!Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1132295768831900312005-11-18T01:36:00.000-05:002005-11-18T01:36:00.000-05:00Infact, a stronger result P^H = PSPACE^H holds. I ...Infact, a stronger result P^H = PSPACE^H holds. <BR/><BR/>I am not sure, but this paper "E. Allender, H. Buhrman, M. Koucky, D. van Melkebeek, and D. Ronneburger. Power from Random Strings. In Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science" does talk about it. <BR/><BR/>The whole idea is to count the number of queries of the PSPACE machine that are answered in "yes" using binary search and then using Immerman Szelepcsenyi kind of approach simulate the PSPACE^H computation by a P machine with H as an oracle. The proof is definetely not as simple as the other one P^PSPACE = NP^PSPACE.<BR/><BR/>It appeared as a qualifyng exam problem at UW Madison. <BR/><BR/>--AnandAnonymousnoreply@blogger.com