tag:blogger.com,1999:blog-3722233.post5507107374960258843..comments2024-03-28T14:56:46.834-05:00Comments on Computational Complexity: Randomness in MadisonLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger1125tag:blogger.com,1999:blog-3722233.post-81922411995033425402009-05-31T01:48:35.079-05:002009-05-31T01:48:35.079-05:00How come nobody every tells me about these things?...How come nobody every tells me about these things??<br /><br /><br />Here's how one could construct such an oracle A. For the moment, drop the requirement that A must be computably enumerable (this could be brought back in using a finite injury argument). Let M_1, M_2, ... be a enumeration of polynomial-time machines with oracle A, and let C_1, C_2, ... be the computably enumerable sets. We attempt to satisfy "Requirement R_[e,i]": M_e is not the characteristic function of C_i for every pair [e,i]. For each pair [e,i], search for a string sigma extending the current oracle A_s which witnesses that M_e does not equal the characteristic function for C_i. If such a sigma is found, then set A_{s+1} to be sigma. Otherwise do nothing and look at the next pair [e,i]. This construction can be achieved using a halting set oracle.<br /><br />If sigma is found then R_[e,i] is satisfied forever. If sigma is not found then the oracle A has no bearing on the output of M_e(x) for large x. In the latter case, M_e must be polynomial-time computable. So either M_e will differ from the characteristic function of every computable set, or else it's polynomial-time computable, as desired.Teutschhttps://www.blogger.com/profile/04848264673734802964noreply@blogger.com