Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with minimal unsatisfiability:
TR03-002 | 13th December 2002
Stefan Szeider

Minimal unsatisfiable formulas with bounded clause-variable difference are fixed-parameter tractable

Revisions: 1

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 >>>

TR09-100 | 16th October 2009
Jakob Nordström, Alexander Razborov

On Minimal Unsatisfiability and Time-Space Trade-offs for $k$-DNF Resolution

In the context of proving lower bounds on proof space in $k$-DNF
resolution, [Ben-Sasson and Nordström 2009] introduced the concept of
minimally unsatisfiable sets of $k$-DNF formulas and proved that a
minimally unsatisfiable $k$-DNF set with $m$ formulas can have at most
$O((mk)^{k+1})$ variables. They also gave an example of ... more >>>

ISSN 1433-8092 | Imprint