[Zurück]

I. Kanj, S. Szeider:
"Parameterized and subexponential-time complexity ofsatisfiability problems and applications";
Theoretical Computer Science, 607 (2015), S. 282 - 295.

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.

http://dx.doi.org/10.1016/j.tcs.2015.08.029