Penn Arts & Sciences Logo

Logic and Computation Seminar

Monday, March 22, 2004 - 4:30pm

Jan Krajicek

Mathematical Institute of the Czech Academy of Sciences and IAS

Location

University of Pennsylvania

DRL 4C8

I shall describe several main conjectures in complexity theory and discuss whether there is a common "hardness assumption" behind them (or few of such assumptions of a "similar" nature). I will look in some detail at proof complexity (i.e., the NP/coNP problem). The talk does not presuppose deeper knowledge of complexity theory than basic definitions.