[an error occurred while processing this directive]
An error occured whilst processing this directive
Abstract
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.
An error occured whilst processing this directive