Disjoint NP-Pairs and Propositional Proof Systems
Christian Glaßer, A. Hughes, Alan L. Selman, Nils Wisiol · ACM SIGACT News · 2014
This article surveys results on disjoint NP-pairs, propositional proof systems, function classes, and promise classes|including results that demonstrate close connections that bind these topics together. We illustrate important links between the questions of whether these classes have complete objects and whether optimal proof systems may exist.