Remember Me
Or use your Academic/Social account:


Or use your Academic/Social account:


You have just completed your registration at OpenAire.

Before you can login to the site, you will need to activate your account. An e-mail will be sent to you with the proper instructions.


Please note that this site is currently undergoing Beta testing.
Any new content you create is not guaranteed to be present to the final version of the site upon release.

Thank you for your patience,
OpenAire Dev Team.

Close This Message


Verify Password:
Verify E-mail:
*All Fields Are Required.
Please Verify You Are Human:
fbtwitterlinkedinvimeoflicker grey 14rssslideshare1
Beyersdorff, O; Mueller, S (2008)
Publisher: Springer Verlag
Languages: English
Types: Other
Cook and Krajíček [9] have obtained the following Karp-Lipton result in bounded arithmetic: if the theory proves , then collapses to , and this collapse is provable in . Here we show the converse implication, thus answering an open question from [9]. We obtain this result by formalizing in a hard/easy argument of Buhrman, Chang, and Fortnow [3]. In addition, we continue the investigation of propositional proof systems using advice, initiated by Cook and Krajíček [9]. In particular, we obtain several optimal and even p-optimal proof systems using advice. We further show that these p-optimal systems are equivalent to natural extensions of Frege systems.
  • The results below are discovered through our pilot algorithms. Let us know how we are doing!

    • 1. J. L. Balc´azar, J. D´ıaz, and J. Gabarr´o. Structural Complexity I. Springer-Verlag, Berlin Heidelberg, 1988.
    • 2. R. Beigel. Bounded queries to SAT and the Boolean hierarchy. Theoretical Computer Science, 84:199-223, 1991.
    • 3. H. Buhrman, R. Chang, and L. Fortnow. One bit of advice. In Proc. 20th Symposium on Theoretical Aspects of Computer Science, pages 547-558, 2003.
    • 4. J.-Y. Cai. S2p ⊆ ZP P NP . Journal of Computer and System Sciences, 73(1):25-35, 2007.
    • 5. J.-Y. Cai, V. T. Chakaravarthy, L. A. Hemaspaandra, and M. Ogihara. Competing provers yield improved Karp-Lipton collapse results. Information and Computation, 198(1):1-23, 2005.
    • 6. R. Chang and J. Kadin. The Boolean hierarchy and the polynomial hierarchy: A closer connection. SIAM Journal on Computing, 25(2):340-354, 1996.
    • 7. S. A. Cook. Feasibly constructive proofs and the propositional calculus. In Proc. 7th Annual ACM Symposium on Theory of Computing, pages 83-97, 1975.
    • 8. S. A. Cook. Theories for complexity classes and their propositional translations. In J. Kraj´ıˇcek, editor, Complexity of Computations and Proofs, pages 175-227. Quaderni di Matematica, 2005.
    • 9. S. A. Cook and J. Kraj´ıˇcek. Consequences of the provability of N P ⊆ P/poly. The Journal of Symbolic Logic, 72(4):1353-1371, 2007.
    • 10. S. A. Cook and P. Nguyen. Foundations of proof complexity: Bounded arithmetic and propositional translations. Book in progress, Available from http://www.cs.toronto.edu/˜sacook.
    • 11. S. A. Cook and R. A. Reckhow. The relative efficiency of propositional proof systems. The Journal of Symbolic Logic, 44:36-50, 1979.
    • 12. L. Fortnow and A. R. Klivans. NP with small advice. In Proc. 20th Annual IEEE Conference on Computational Complexity, pages 228-234, 2005.
    • 13. E. Jeˇr´abek. Approximate counting by hashing in bounded arithmetic. Preprint, 2007.
    • 14. J. Kadin. The polynomial time hierarchy collapses if the Boolean hierarchy collapses. SIAM Journal on Computing, 17(6):1263-1282, 1988.
    • 15. R. M. Karp and R. J. Lipton. Some connections between nonuniform and uniform complexity classes. In Proc. 12th ACM Symposium on Theory of Computing, pages 302-309. ACM Press, 1980.
    • 16. J. K¨obler and O. Watanabe. New collapse consequences of NP having small circuits. SIAM Journal on Computing, 28(1):311-324, 1998.
    • 17. J. Kraj´ıˇcek. Bounded Arithmetic, Propositional Logic, and Complexity Theory, volume 60 of Encyclopedia of Mathematics and Its Applications. Cambridge University Press, Cambridge, 1995.
    • 18. J. Kraj´ıˇcek and P. Pudl´ak. Propositional proof systems, the consistency of first order theories and the complexity of computations. The Journal of Symbolic Logic, 54:1063-1079, 1989.
    • 19. J. Kraj´ıˇcek, P. Pudl´ak, and G. Takeuti. Bounded arithmetic and the polynomial hierarchy. Annals of Pure and Applied Logic, 52:143-153, 1991.
    • 20. Z. Sadowski. On an optimal propositional proof system and the structure of easy subsets of TAUT. Theoretical Computer Science, 288(1):181-193, 2002.
    • 21. D. Zambella. Notes on polynomially bounded arithmetic. The Journal of Symbolic Logic, 61(3):942-966, 1996.
  • No related research data.
  • Discovered through pilot similarity algorithms. Send us your feedback.

Share - Bookmark

Cite this article