Survey of Disjoint NP-Pairs and Relations to Propositional Proof Systems
Christian Glaßer, Alan L. Selman, Liyu Zhang · 2005
A disjoint NP-pair is a pair (A,B) of nonempty, disjoint sets A and B such that both A and B belong to the complexity class NP.3 We let DisjNP denote the collection of all disjoint NP-pairs. A separator of a disjoint NP-pair (A,B) is a set S such that A ⊆ S and B ⊆ S (Figure 1). A fundamental question