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.
Logic and Computation Seminar
Monday, March 22, 2004 - 4:30pm
Jan Krajicek
Mathematical Institute of the Czech Academy of Sciences and IAS