<--- Back to Details
| First Page | Document Content | |
|---|---|---|
 Date: 2011-11-07 20:15:16Complexity classes NTIME Circuit complexity P Bounded-error probabilistic polynomial Cook–Levin theorem Time hierarchy theorem NEXPTIME Time complexity Theoretical computer science Computational complexity theory Applied mathematics |
Add to Reading List |
A Casual Tour Around a Circuit Complexity Bound∗ arXiv:1111.1261v1 [cs.CC] 4 Nov 2011 Ryan Williams†
![How hard is it to approximate the Jones polynomial? Greg Kuperberg∗ Department of Mathematics, University of California, Davis, CAarXiv:0908.0512v2 [quant-ph] 27 Oct 2014](https://www.pdfsearch.io/img/027f8fdc8a58ef6c80efa7006c98b68d.jpg "How hard is it to approximate the Jones polynomial? Greg Kuperberg∗ Department of Mathematics, University of California, Davis, CAarXiv:0908.0512v2 [quant-ph] 27 Oct 2014")
![A Counterexample to the Generalized Linial-Nisan Conjecture Scott Aaronson∗ Abstract In earlier work [1], we gave an oracle separating the relational versions of BQP and the polynomial hierarchy, and showed that an ora](https://www.pdfsearch.io/img/1c67cff709195b350a64a8cc8f79e357.jpg "A Counterexample to the Generalized Linial-Nisan Conjecture Scott Aaronson∗ Abstract In earlier work [1], we gave an oracle separating the relational versions of BQP and the polynomial hierarchy, and showed that an ora")