Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with deficiency:
TR00-018 | 16th February 2000
Oliver Kullmann

An application of matroid theory to the SAT problem

A basic property of minimally unsatisfiable clause-sets F is that
c(F) >= n(F) + 1 holds, where c(F) is the number of clauses, and
n(F) the number of variables. Let MUSAT(k) be the class of minimally
unsatisfiable clause-sets F with c(F) <= n(F) + k.

Poly-time decision algorithms are known ... more >>>

TR07-055 | 22nd May 2007
Oliver Kullmann

Constraint satisfaction problems in clausal form: Autarkies and minimal unsatisfiability

Revisions: 1

We consider the next step from boolean conjunctive normal forms to
arbitrary constraint satisfaction problems (with arbitrary constraints), namely "generalised clause-sets" (or "sets of no-goods"), which allow negative literals "v <> e" for variables v and values e --- this level of generality appears to be the right level for ... more >>>

ISSN 1433-8092 | Imprint