Abstract
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.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
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)
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)
Cook, S., Reckhow, R.: The relative efficiency of propositional proof systems. Journal of Symbolic Logic 44, 36–50 (1979)
Even, S., Selman, A., Yacobi, J.: The complexity of promise problems with applications to public-key cryptography. Information and Control 61, 159–173 (1984)
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)
Glaßer, C., Selman, A., Sengupta, S., Zhang, L.: Disjoint NP-pairs. SIAM Journal on Computing 33(6), 1369–1416 (2004)
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)
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)
Grollmann, J., Selman, A.: Complexity measures for public-key cryptosystems. SIAM Journal on Computing 17(2), 309–335 (1988)
Hartmanis, J., Hemachandra, L.A.: Complexity classes without machines: On complete languages for UP. Theoretical Computer Science 58, 129–142 (1988)
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)
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)
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)
Ladner, R.: On the structure of polynomial-time reducibility. Journal of the ACM 22, 155–171 (1975)
Lovász, L.: On the shannon capacity of graphs. IEEE Transactions on Information Theory 25, 1–7 (1979)
Messner, J.: On the Simulation Order of Proof Systems. PhD thesis, Universität Ulm (2000)
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)
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)
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)
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)
Razborov. On provably disjoint NP-pairs. Technical Report TR94-006, Electronic Colloquium on Computational Complexity (1994)
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)
Regan, K.: The topology of provability in complexity theory. Journal of Computer and System Sciences 36, 384–432 (1988)
Sadowski, Z.: On an optimal propositional proof system and the structure of easy subsets of TAUT. Theoretical Computer Science 288(1), 181–193 (2002)
Schöning, U.: A uniform approach to obtain diagonal sets in complexity classes. Theoretical Computer Science 18, 95–103 (1982)
Selman, A.: Promise problems complete for complexity classes. Information and Computation 78, 87–98 (1988)
Valiant, L.G.: Relative complexity of checking and evaluation. Information Processing Letters 5, 20–23 (1976)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this chapter
Cite this chapter
Glaßer, C., Selman, A.L., Zhang, L. (2006). Survey of Disjoint NP-pairs and Relations to Propositional Proof Systems. In: Goldreich, O., Rosenberg, A.L., Selman, A.L. (eds) Theoretical Computer Science. Lecture Notes in Computer Science, vol 3895. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11685654_11
Download citation
DOI: https://doi.org/10.1007/11685654_11
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-32880-3
Online ISBN: 978-3-540-32881-0
eBook Packages: Computer ScienceComputer Science (R0)
Keywords
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.