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 (2006)
Publisher: Springer Verlag
Languages: English
Types: Other
For a proof system P we introduce the complexity class DNPP(P) of all disjoint NP-pairs for which the disjointness of the pair is efficiently provable in the proof system P. We exhibit structural properties of proof systems which make the previously defined canonical NP-pairs of these proof systems hard or complete for DNPP(P). Moreover we demonstrate that non-equivalent proof systems can have equivalent canonical pairs and that depending on the properties of the proof systems different scenarios for DNPP(P) and the reductions between the canonical pairs exist.
  • The results below are discovered through our pilot algorithms. Let us know how we are doing!

    • 1. A. Atserias and M. L. Bonet. On the automatizability of resolution and related propositional proof systems. In Computer Science Logic, 16th International Workshop, pages 569-583, 2002.
    • 2. O. Beyersdorff. Representable disjoint NP-pairs. In Proc. 24th Conference on Foundations of Software Technology and Theoretical Computer Science, pages 122- 134, 2004.
    • 3. O. Beyersdorff. Disjoint NP-pairs from propositional proof systems. Technical Report TR05-083, Electronic Colloquium on Computational Complexity, 2005.
    • 4. M. L. Bonet, T. Pitassi, and R. Raz. Lower bounds for cutting planes proofs with small coefficients. The Journal of Symbolic Logic, 62(3):708-728, 1997.
    • 5. M. L. Bonet, T. Pitassi, and R. Raz. On interpolation and automatization for Frege systems. SIAM Journal on Computing, 29(6):1939-1967, 2000.
    • 6. S. R. Buss. Bounded Arithmetic. Bibliopolis, Napoli, 1986.
    • 7. S. A. Cook and R. A. Reckhow. The relative efficiency of propositional proof systems. The Journal of Symbolic Logic, 44:36-50, 1979.
    • 8. C. Glaßer, A. L. Selman, and S. Sengupta. Reductions between disjoint NP-pairs. In Proc. 19th Annual IEEE Conference on Computational Complexity, pages 42- 53, 2004.
    • 9. C. Glaßer, A. L. Selman, S. Sengupta, and L. Zhang. Disjoint NP-pairs. SIAM Journal on Computing, 33(6):1369-1416, 2004.
    • 10. C. Glaßer, A. L. Selman, and L. Zhang. Canonical disjoint NP-pairs of propositional proof systems. In Proc. 30th International Symposium on the Mathematical Foundations of Computer Science, pages 399-409, 2005.
    • 11. J. Grollmann and A. L. Selman. Complexity measures for public-key cryptosystems. SIAM Journal on Computing, 17(2):309-335, 1988.
    • 12. S. Homer and A. L. Selman. Oracles for structural properties: The isomorphism problem and public-key cryptography. Journal of Computer and System Sciences, 44(2):287-301, 1992.
    • 13. J. K¨obler, J. Messner, and J. Tor´an. Optimal proof systems imply complete sets for promise classes. Information and Computation, 184:71-92, 2003.
    • 14. J. Kraj´ıˇcek. Bounded Arithmetic, Propositional Logic, and Complexity Theory, volume 60 of Encyclopedia of Mathematics and Its Applications. Cambridge University Press, Cambridge, 1995.
    • 15. J. Kraj´ıˇcek. Interpolation theorems, lower bounds for proof systems and independence results for bounded arithmetic. The Journal of Symbolic Logic, 62(2):457- 486, 1997.
    • 16. J. Kraj´ıˇcek. Dual weak pigeonhole principle, pseudo-surjective functions, and provability of circuit lower bounds. The Journal of Symbolic Logic, 69(1):265-286, 2004.
    • 17. 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:1963-1079, 1989.
    • 18. J. Kraj´ıˇcek and P. Pudl´ak. Quantified propositional calculi and fragments of bounded arithmetic. Zeitschrift fu¨r mathematische Logik und Grundlagen der Mathematik, 36:29-46, 1990.
    • 19. J. Kraj´ıˇcek and P. Pudl´ak. Some consequences of cryptographical conjectures for S1 2 and EF . Information and Computation, 140(1):82-94, 1998.
    • 20. P. Pudl´ak. Lower bounds for resolution and cutting planes proofs and monotone computations. The Journal of Symbolic Logic, 62:981-998, 1997.
    • 21. P. Pudl´ak. On reducibility and symmetry of disjoint NP-pairs. Theoretical Computer Science, 295:323-339, 2003.
    • 22. A. A. Razborov. On provably disjoint NP-pairs. Technical Report TR94-006, Electronic Colloquium on Computational Complexity, 1994.
  • No related research data.
  • Discovered through pilot similarity algorithms. Send us your feedback.

Share - Bookmark

Cite this article