http://openproblemgarden.org/op/unconditional_derandomization_of_mathcal_am Comments for "Unconditional derandomization of Arthur-Merlin games" en http://openproblemgarden.org/op/unconditional_derandomization_of_mathcal_am <table cellspacing="10"> <tr> <td> Author(s): <a href="/category/shaltiel_ronen">Shaltiel</a>; <a href="/category/umans_christopher">Umans</a>&nbsp;&nbsp; </td> <td align=right> Subject: <a href="/category/theoretical_computer_science">Theoretical Comp. Sci.</a> » <a href="/category/complexity">Complexity</a> » <a href="/category/derandomization">Derandomization</a>&nbsp;&nbsp; </td> </tr> <tr> <td colspan=2> <table border=1 cellspacing="5"> <tr><td> <div class="envtheorem"><b>Problem</b>&nbsp;&nbsp; Prove <em>unconditionally</em> that <a href="http://en.wikipedia.org/wiki/Arthur-Merlin_protocol"><img class="teximage" src="/files/tex/1018c4ff8a3a6c7d67c8002ae0271627c9a635f2.png" alt="$ \mathcal{AM} $" /></a> <img class="teximage" src="/files/tex/b25da1edfbc42e01d22392d6057b4adcff3d9593.png" alt="$ \subseteq $" /> <a href="http://en.wikipedia.org/wiki/Polynomial_hierarchy"><img class="teximage" src="/files/tex/f39c4db14cdd670e812c7e2fabfb781cc40c61df.png" alt="$ \Sigma_2 $" /></a>. </div> </tr></td> </table> </td> </tr> </table> Shaltiel, Ronen Umans, Christopher Arthur-Merlin Hitting Sets unconditional Theoretical Computer Science Complexity Derandomization http://openproblemgarden.org/op/unconditional_derandomization_of_mathcal_am#comment Mon, 16 Jul 2007 12:06:44 +0200 ormeir 454 at http://openproblemgarden.org