LFCS Seminar

Disjoint NP-Pairs

Alan Selman

State University of New York--Buffalo

4pm Tuesday 7th March 2006
Room 2511, JCMB, King's Buildings

---

Abstract

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, and disjoint NP-pairs arise naturally in the study of propositional proof systems. This talk will focus primarily on connections of disjoint NP-pairs with propositional proof systems. I will survey results and open questions.