Login
Computer Science @ Rochester
Monday, October 20, 2003
11:00 AM
CSB 209
Alan L. Selman
U. Buffalo
Disjoint NP-Pairs
A disjoint NP-pair is a pair (A, B) of nonempty, disjoint sets such that both A and B belong to NP. Given a disjoint NP pair, we are interested in whether there is a set S in P that separates them: S separates (A, B) if A is a subset of S and B is a subset of the complement of S.

The existence of disjoint pairs that are not separated by any set in P is closely connected to the existence of public-key cryptosystems. Also, disjoint pairs arise naturally in the study of propositional proof systems. This talk will explain these connections and will survey several results.