Parameterized and subexponential-time complexity of satisfiability problems and applications
| Autor: | Stefan Szeider, Iyad A. Kanj |
|---|---|
| Rok vydání: | 2015 |
| Předmět: |
Discrete mathematics
General Computer Science Boolean circuit Parameterized complexity Computer Science::Computational Complexity Satisfiability Theoretical Computer Science Structural complexity theory Computer Science::Emerging Technologies TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY Maximum satisfiability problem Worst-case complexity Circuit complexity Computer Science::Data Structures and Algorithms Time complexity MathematicsofComputing_DISCRETEMATHEMATICS Mathematics |
| Zdroj: | Theoretical Computer Science. 607:282-295 |
| ISSN: | 0304-3975 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect