Stefan Szeider

The deficiency of a propositional formula F in CNF with n variables

and m clauses is defined as m-n. It is known that minimal

unsatisfiable formulas (unsatisfiable formulas which become

satisfiable by removing any clause) have positive deficiency.

Recognition of minimal unsatisfiable formulas is NP-hard, and it was

shown recently ...
more >>>

Yuan Li, Alexander Razborov, Benjamin Rossman

Let $P$ be a fixed graph (hereafter called a ``pattern''), and let

$Subgraph(P)$ denote the problem of deciding whether a given graph $G$

contains a subgraph isomorphic to $P$. We are interested in

$AC^0$-complexity of this problem, determined by the smallest possible exponent

$C(P)$ for which $Subgraph(P)$ possesses bounded-depth circuits ...
more >>>