[Colloquium] Reminder: Alan Selman Talk TTI today 2:00pm

[Katherine Cumming]

Alan Selman
SUNY at Buffalo

Disjoint NP-Pairs
 
Monday, November 15th 2004
 
TTI-C 2:00 pm
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 with disjoint
NP-pairs and propositional proofs systems. I will survey results and
open questions.
 
 
 
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20041115/b2c0f807/attachment.htm