Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

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