tag:blogger.com,1999:blog-3722233.post85517236..comments2024-03-28T18:17:00.135-05:00Comments on Computational Complexity: Foundations of ComplexityLesson 3: Universal Turing Machines and DiagonalizationLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger4125tag:blogger.com,1999:blog-3722233.post-21336133899209886682010-08-09T14:28:58.666-05:002010-08-09T14:28:58.666-05:00Thanks!Thanks!Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-66100905771936168772010-08-06T09:36:19.782-05:002010-08-06T09:36:19.782-05:00The rule is all machines must have access to oracl...The rule is all machines must have access to oracle B. So in (P^NP)^B both the P and NP machines have access to B, think ((P^B)^(NP^B)). Now the P machine can access B through the NP machine so this is the same as P^(NP^B).Lance Fortnowhttps://www.blogger.com/profile/06752030912874378610noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-81553108136250891132010-07-27T04:45:47.877-05:002010-07-27T04:45:47.877-05:00Hi, I'm studying some topics of computational ...Hi, I'm studying some topics of computational complexity now, and there is one thing that seems hard to understand regarding relativization. I know it is not the right place to post this, but I think it is somehow related to diagonalization. So, here is my question:<br /><br />Take for instance the class C=P^NP, and a language B. How are the oracle machines from C^B working? <br />- are they deterministic polytime machines that ask queries from NP^B?<br />- are they deterministic polytime machines that ask queries to both B and NP?<br /><br />Thanks!Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-67258771475079069572010-03-03T01:21:47.716-06:002010-03-03T01:21:47.716-06:00Already stuck on lesson 3... have not halted, acce...Already stuck on lesson 3... have not halted, accepted or rejected after 1 day. Continuing processing. Thanks for the lessons!Anonymousnoreply@blogger.com