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.
Important!
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.
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.
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.
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.