Personal tools
You are here: Home Events Abstract Archives 2006-2007 Disjoint NP-Pairs

Disjoint NP-Pairs

Alan Selman State University of New York--Buffalo 4pm Tuesday 7th March 2006 Room 2511, JCMB, King's Buildings

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.

Document Actions