Notice
This item was automatically migrated from a legacy system. It's data has not been checked and might not meet the quality criteria of the present system.
Kanj, I., & Szeider, S. (2015). Parameterized and subexponential-time complexity ofsatisfiability problems and applications. Theoretical Computer Science, 607, 282–295. https://doi.org/10.1016/j.tcs.2015.08.029
E192-01 - Forschungsbereich Algorithms and Complexity
-
Journal:
Theoretical Computer Science
-
ISSN:
0304-3975
-
Date (published):
2015
-
Number of Pages:
14
-
Publisher:
ELSEVIER
-
Peer reviewed:
Yes
-
Keywords:
Theoretical Computer Science; General Computer Science
-
Abstract:
We study the parameterized and the subexponential-time complexity of the weighted and the unweighted satisfiability problems on bounded-depth normalized Boolean circuits. We establish relations between the subexponential-time complexity of the weighted and the unweighted satisfiability problems, and use them to derive relations among the subexponential-time complexity of several NP-hard problem. W...
We study the parameterized and the subexponential-time complexity of the weighted and the unweighted satisfiability problems on bounded-depth normalized Boolean circuits. We establish relations between the subexponential-time complexity of the weighted and the unweighted satisfiability problems, and use them to derive relations among the subexponential-time complexity of several NP-hard problem. We then study the role of certain natural structural parameters of the circuit in characterizing the parameterized and the subexponential-time complexity of the circuit satisfiability problems under consideration. We obtain threshold functions on some circuit structural parameters, including the depth, the number of gates, the fan-in, and the maximum number of (variable) occurrences, that lead to tight characterizations of the parameterized and the subexponential-time complexity of the circuit satisfiability problems under consideration.
