Wyniki wyszukiwania - BazTech

Ograniczanie wyników

2 Fundamenta Informaticae

Znaleziono wyników: 2

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: parameterized complexity

Sortuj według:

Ogranicz wyniki do:

Parameterized Complexity of Weighted Satisfiability Problems : Decision, Enumeration, Counting

Creignou N., Vollmer H.

Fundamenta Informaticae

2015

Vol. 136, nr 4

297--316

We consider the weighted satisfiability problem for Boolean circuits and propositional formulæ, where the weight of an assignment is the number of variables set to true. We study the parameterized complexity of these problems and initiate a systematic study of the complexity of its fragments. Only the monotone fragment has been considered so far and proven to be of same complexity as the unrestricted problems. Here, we consider all fragments obtained by semantically restricting circuits or formulæ to contain only gates (connectives) from a fixed set B of Boolean functions. We obtain a dichotomy result by showing that for each such B, the weighted satisfiability problems are either W[P]-complete (for circuits) or W[SAT]-complete (for formulæ) or efficiently solvable. We also consider the related enumeration and counting problems.

Better Algorithms for Satisfiability Problems for Formulas of Bounded Rank-width

Ganian R., Hlinĕný P., Obdržálek J.

Fundamenta Informaticae

2013

Vol. 123, nr 1

59--76

We provide a parameterized algorithm for the propositional model counting problem #SAT, the runtime of which has a single-exponential dependency on the rank-width of the signed graph of a formula. That is, our algorithm runs in time O(t3 · 23t(t+1)/2 ·|φ| for a width-t rankdecomposition of the input φ, and can be of practical interest for small values of rank-width. Previously, analogical algorithms have been known – e.g. [Fischer, Makowsky, and Ravve] – with a single-exponential dependency on the clique-width k of the signed graph of a formula with a given k-expression. Our algorithm presents an exponential runtime improvement over the worst-case scenario of the previous one, since clique-width reaches up to exponentially higher values than rankwidth. We also provide an algorithm for the MAX-SAT problem along the same lines.