Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > SATISFIABILITY PROBLEMS:
Reports tagged with satisfiability problems:
TR98-022 | 14th April 1998
Steffen Reith, Heribert Vollmer

#### The Complexity of Computing Optimal Assignments of Generalized Propositional Formulae

We consider the problems of finding the lexicographically
minimal (or maximal) satisfying assignment of propositional
formulae for different restricted formula classes. It turns
out that for each class from our framework, the above problem
is either polynomial time solvable or complete for ... more >>>

TR04-051 | 10th June 2004
Zdenek Dvorák, Daniel Král, Ondrej Pangrác

#### Locally consistent constraint satisfaction problems

An instance of a constraint satisfaction problem is $l$-consistent
if any $l$ constraints of it can be simultaneously satisfied.
For a set $\Pi$ of constraint types, $\rho_l(\Pi)$ denotes the largest ratio of constraints which can be satisfied in any $l$-consistent instance composed by constraints from the set $\Pi$. In the ... more >>>

TR07-023 | 26th February 2007
Heribert Vollmer, Michael Bauland, Elmar Böhler, Nadia Creignou, Steffen Reith, Henning Schnoor

#### The Complexity of Problems for Quantified Constraints

In this paper we will look at restricted versions of the evaluation problem, the model checking problem, the equivalence problem, and the counting problem for quantified propositional formulas, both with and without bound on the number of quantifier alternations. The restrictions are such that we consider formulas in conjunctive normal-form ... more >>>

ISSN 1433-8092 | Imprint