tag:blogger.com,1999:blog-3722233.post200060468..comments2024-04-18T20:56:23.855-05:00Comments on Computational Complexity: The Berman-Hartmanis Isomorphism ConjectureLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger1125tag:blogger.com,1999:blog-3722233.post-22507364995281437382007-10-03T19:50:00.000-05:002007-10-03T19:50:00.000-05:00This post left open the question of why researcher...This post left open the question of why researchers believe the isomorphism conjecture is false. The most compelling evidence that I'm aware of was presented in "The isomorphism conjecture fails relative to a random oracle" by Kurtz, Mahaney, and Royer, which asserts what its title says. Moreover they make the claim that although some results hold in the unrelativized case but not for a random oracle (like IP=PSPACE), they believe that the isomorphism conjecture does fail in the unrelativized case. Here is their argument:<BR/><BR/>"Both counterexamples [to the random oracle conjecture] have a common flavor. Imagine that there are exponentially many boxes, one of which contains a prize. If the prize is placed at random, then a computational agent that can only examine polynomially many boxes has essentially no chance of finding the prize, no matter how powerful he may be. If, on the other hand, the prize is placed only pseudorandomly, then a sufficiently powerful computational agent will find it every time. Both counterexamples rely on finding computational agents (P^SAT or IP) that are strong enough to defeat any polynomial time pseudorandom prize-hiding strategy; but these agents must themselves be defeated when presented with a truly random prize-hiding strategy. [...] In our case, the computational agents we will consider will be in P, and so, in some sense, we end up relying on the fact that P^R isn't powerful enough to search R. But now we're back to the observation upon which the random oracle conjecture was based: there seem to be good pseudorandom languages in P, and we only need them to be good enough to defeat P, not P^SAT or IP. We believe that such pseudorandom languages exist, and that therefore the unrelativized isomorphism conjecture fails."D Coetzeehttps://www.blogger.com/profile/05407492273389264037noreply@blogger.com