Survey of Disjoint NP-pairs and Relations to Propositional Proof Systems

  • Christian Glaßer
  • Alan L. Selman
  • Liyu Zhang
Part of the Lecture Notes in Computer Science book series (LNCS, volume 3895)


We survey recent results on disjoint NP-pairs. In particular, we survey the relationship of disjoint NP-pairs to the theory of proof systems for propositional calculus.


Turing Machine Proof System Disjunctive Normal Form Canonical Pair Degree Structure 
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.


Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.


  1. 1.
    Ben-David, S., Gringauze, A.: On the existence of propositional proof systems and oracle-relativized propositional logic. Technical Report 5, Electronic Colloquium on Computational Complexity (1998)Google Scholar
  2. 2.
    Buhrman, H., Fenner, S., Fortnow, L., van Melkebeek, D.: Optimal proof systems and sparse sets. In: Reichel, H., Tison, S. (eds.) STACS 2000. LNCS, vol. 1770, pp. 407–418. Springer, Heidelberg (2000)CrossRefGoogle Scholar
  3. 3.
    Cook, S., Reckhow, R.: The relative efficiency of propositional proof systems. Journal of Symbolic Logic 44, 36–50 (1979)zbMATHCrossRefMathSciNetGoogle Scholar
  4. 4.
    Even, S., Selman, A., Yacobi, J.: The complexity of promise problems with applications to public-key cryptography. Information and Control 61, 159–173 (1984)zbMATHCrossRefMathSciNetGoogle Scholar
  5. 5.
    Glaßer, C., Selman, A., Sengupta, S.: Reductions between disjoint NP-pairs. In: Proceedings 19th IEEE Conference on Computational Complexity, pp. 42–53. IEEE Computer Society Press, Los Alamitos (2004)CrossRefGoogle Scholar
  6. 6.
    Glaßer, C., Selman, A., Sengupta, S., Zhang, L.: Disjoint NP-pairs. SIAM Journal on Computing 33(6), 1369–1416 (2004)zbMATHCrossRefMathSciNetGoogle Scholar
  7. 7.
    Glaßer, C., Selman, A., Zhang, L.: Canonical disjoint NP-pairs of proposional proof systems. Technical Report 04-106, Electronic Colloquium on Computational Complexity (2004)Google Scholar
  8. 8.
    Goldreich, O.: On promise problems: A survey. In: Goldreich, O., Rosenberg, A.L., Selman, A.L. (eds.) Theoretical Computer Science. LNCS, vol. 3895, pp. 254–290. Springer, Heidelberg (2006)CrossRefGoogle Scholar
  9. 9.
    Grollmann, J., Selman, A.: Complexity measures for public-key cryptosystems. SIAM Journal on Computing 17(2), 309–335 (1988)zbMATHCrossRefMathSciNetGoogle Scholar
  10. 10.
    Hartmanis, J., Hemachandra, L.A.: Complexity classes without machines: On complete languages for UP. Theoretical Computer Science 58, 129–142 (1988)zbMATHCrossRefMathSciNetGoogle Scholar
  11. 11.
    Homer, S., Selman, A.: Oracles for structural properties: The isomorphism problem and public-key cryptography. Journal of Computer and System Sciences 44(2), 287–301 (1992)zbMATHCrossRefMathSciNetGoogle Scholar
  12. 12.
    Köbler, J., Messner, J., Torán, J.: Optimal proof systems imply complete sets for promise classes. Information and Computation 184(1), 71–92 (2003)zbMATHCrossRefMathSciNetGoogle Scholar
  13. 13.
    Krajíček, J., Pudlák, P.: Propositional proof systems, the consistency of first order theories and the complexity of computations. Journal of Symbolic Logic 54, 1063–1079 (1989)zbMATHCrossRefMathSciNetGoogle Scholar
  14. 14.
    Ladner, R.: On the structure of polynomial-time reducibility. Journal of the ACM 22, 155–171 (1975)zbMATHCrossRefMathSciNetGoogle Scholar
  15. 15.
    Lovász, L.: On the shannon capacity of graphs. IEEE Transactions on Information Theory 25, 1–7 (1979)zbMATHCrossRefGoogle Scholar
  16. 16.
    Messner, J.: On the Simulation Order of Proof Systems. PhD thesis, Universität Ulm (2000)Google Scholar
  17. 17.
    Messner, J.: On the structure of the simulation order of proof systems. In: Brim, L., Gruska, J., Zlatuška, J. (eds.) MFCS 1998. LNCS, vol. 1450, pp. 581–592. Springer, Heidelberg (1998)Google Scholar
  18. 18.
    Meßner, J., Torán, J.: Optimal proof systems for propositional logic and complete sets. In: Proceedings 15th Symposium on Theoretical Aspects of Computer Science, Lecture Notes in Computer Science. LNCS, pp. 477–487. Springer, Heidelberg (1998)Google Scholar
  19. 19.
    Pudlák, P.: On the length of proofs of finitistic consistency statements in first order theories. In: Paris, J.B., et al. (eds.) Logic Colloquium 1984, pp. 165–196. North-Holland, Amsterdam (1986)Google Scholar
  20. 20.
    Pudlák, P.: On reducibility and symmetry of disjoint NP-pairs. In: Sgall, J., Pultr, A., Kolman, P. (eds.) MFCS 2001. LNCS, vol. 2136, pp. 621–632. Springer, Heidelberg (2001)CrossRefGoogle Scholar
  21. 21.
    Razborov. On provably disjoint NP-pairs. Technical Report TR94-006, Electronic Colloquium on Computational Complexity (1994)Google Scholar
  22. 22.
    Regan, K.: On diagonalization methods and the structure of language classes. In: Karpinski, M. (ed.) FCT 1983. LNCS, vol. 158, pp. 368–380. Springer, Heidelberg (1983)Google Scholar
  23. 23.
    Regan, K.: The topology of provability in complexity theory. Journal of Computer and System Sciences 36, 384–432 (1988)CrossRefMathSciNetGoogle Scholar
  24. 24.
    Sadowski, Z.: On an optimal propositional proof system and the structure of easy subsets of TAUT. Theoretical Computer Science 288(1), 181–193 (2002)zbMATHCrossRefMathSciNetGoogle Scholar
  25. 25.
    Schöning, U.: A uniform approach to obtain diagonal sets in complexity classes. Theoretical Computer Science 18, 95–103 (1982)zbMATHCrossRefMathSciNetGoogle Scholar
  26. 26.
    Selman, A.: Promise problems complete for complexity classes. Information and Computation 78, 87–98 (1988)zbMATHCrossRefMathSciNetGoogle Scholar
  27. 27.
    Valiant, L.G.: Relative complexity of checking and evaluation. Information Processing Letters 5, 20–23 (1976)zbMATHCrossRefMathSciNetGoogle Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2006

Authors and Affiliations

  • Christian Glaßer
    • 1
  • Alan L. Selman
    • 2
  • Liyu Zhang
    • 2
  1. 1.Theoretische InformatikUniversität WürzburgWürzburgGermany
  2. 2.Department of Computer Science and EngineeringUniversity at BuffaloBuffaloUSA

Personalised recommendations