A. Stephen, J. Cook, and . Krají?ek, Consequences of the provability of N P ? P/poly, The Journal of Symbolic Logic, vol.72, issue.4, pp.1353-1371, 2007.

A. Stephen, R. A. Cook, and . Reckhow, The relative efficiency of propositional proof systems, The Journal of Symbolic Logic, vol.44, issue.1, pp.36-50, 1979.

L. Fortnow and R. Santhanam, Hierarchy Theorems for Probabilistic Polynomial Time, 45th Annual IEEE Symposium on Foundations of Computer Science, pp.316-324, 2004.
DOI : 10.1109/FOCS.2004.33

L. Fortnow and R. Santhanam, Recent work on hierarchies for semantic classes, SIGACT News, vol.37, issue.3, pp.36-54, 2006.

D. Grigoriev, E. A. Hirsch, and K. Pervyshev, A Complete Public-Key Cryptosystem, Groups ??? Complexity ??? Cryptology, vol.1, issue.1, pp.1-12, 2009.
DOI : 10.1515/GCC.2009.1

URL : https://hal.archives-ouvertes.fr/hal-00714336

D. Harnik, J. Kilian, M. Naor, O. Reingold, and A. Rosen, On Robust Combiners for Oblivious Transfer and Other Primitives, Proc. of EUROCRYPT-2005, 2005.
DOI : 10.1007/11426639_6

M. Dmitry and . Itsykson, Structural complexity of AvgBPP, Proceedings of 4th International Computer Science Symposium in Russia, pp.155-166, 2009.

J. Krají?ek and P. Pudlák, Abstract, The Journal of Symbolic Logic, vol.1130, issue.03, pp.1063-1079, 1989.
DOI : 10.1016/0304-3975(85)90144-6

L. A. Levin, Universal sequential search problems. Problems of Information Transmission, pp.265-266, 1973.

J. Messner, On Optimal Algorithms and Optimal Proof Systems, Proceedings of the 16th Symposium on Theoretical Aspects of Computer Science, pp.361-372, 1999.
DOI : 10.1007/3-540-49116-3_51

[. Monroe, Speedup for natural problems and coNP?=NP, Electronic Colloquium on Computational Complexity, 2009.

R. Motwani and P. Raghavan, Randomized algorithms, 1995.

K. Pervyshev, On Heuristic Time Hierarchies, Twenty-Second Annual IEEE Conference on Computational Complexity (CCC'07), pp.347-358, 2007.
DOI : 10.1109/CCC.2007.20

P. Pudlák, On reducibility and symmetry of disjoint NP pairs, Theoretical Computer Science, vol.295, pp.1-3323, 2003.

A. A. Razborov, On provably disjoint NP-pairs, BRICS Report Series, vol.1, issue.36, 1994.
DOI : 10.7146/brics.v1i36.21607