Oliver Kullmann

A relativized hierarchy of conjunctive normal forms

is introduced, recognizable and SAT decidable in polynomial

time. The corresponding hardness parameter, the first level

of inclusion in the hierarchy, is studied in detail, admitting

several characterizations, e.g., using pebble games, the space

complexity of (relativized) tree-like ...
more >>>

Juan Luis Esteban, Jacobo Toran

We show that the Player-Adversary game from a paper

by Pudlak and Impagliazzo played over

CNF propositional formulas gives

an exact characterization of the space needed

in treelike resolution refutations. This

characterization is purely combinatorial

and independent of the notion of resolution.

We use this characterization to give ...
more >>>

Noah Fleming, Stefan Grosser, Mika Göös, Robert Robere

We give a new characterization of the Sherali-Adams proof system, showing that there is a degree-$d$ Sherali-Adams refutation of an unsatisfiable CNF formula $C$ if and only if there is an $\varepsilon > 0$ and a degree-$d$ conical junta $J$ such that $viol_C(x) - \varepsilon = J$, where $viol_C(x)$ counts ... more >>>