# The finite model theory of random 3-CNF formulas

Albert Atserias Universitat Politecnica de Catalunya 4pm Tuesday 14th February 2006 Room 2511, JCMB, King's Buildings

The model of random 3-CNF formulas has received attention from several different communities: from AI to statistical mechanics, through complexity theory and logic. It parallels the classical theory of random graphs, but of course the focus is set on studying satisfiability rather than other classical graph or hypergraph invariants. In this talk I will overview the complexity-theoretic side of the area, with a focus on descriptive complexity. How do we certify that a particular given random formula is unsatisfiable? Despite we know that most are unsatisfiable by a counting argument, it is not clear how to actually prove that any particular one is.