Title: Disjoint NP-pairs and Propositional Proof Systems
Speaker: Alan Selman, University of Buffalo
Date: Wednesday, November 5, 2014 11:00-12:00pm
Location: CoRE Bldg, Room 301A, Rutgers University, Busch Campus, Piscataway, NJ
This talk surveys results on disjoint NP-pairs, propositional proof systems, function classes, and promise classes - including results that demonstrate close connections that bind these topics together. We illustrate important links between the questions of whether these classes have complete objects and whether optimal proof systems may exist.