000 03438nam a22005415i 4500
001 978-3-662-60670-4
003 DE-He213
005 20240423125031.0
007 cr nn 008mamaa
008 191230s2019 gw | s |||| 0|eng d
020 _a9783662606704
_9978-3-662-60670-4
024 7 _a10.1007/978-3-662-60670-4
_2doi
050 4 _aQA8.9-10.3
072 7 _aPBCD
_2bicssc
072 7 _aPBC
_2bicssc
072 7 _aMAT018000
_2bisacsh
072 7 _aPBCD
_2thema
072 7 _aPBC
_2thema
082 0 4 _a511.3
_223
100 1 _ade Haan, Ronald.
_eauthor.
_4aut
_4http://id.loc.gov/vocabulary/relators/aut
245 1 0 _aParameterized Complexity in the Polynomial Hierarchy
_h[electronic resource] :
_bExtending Parameterized Complexity Theory to Higher Levels of the Hierarchy /
_cby Ronald de Haan.
250 _a1st ed. 2019.
264 1 _aBerlin, Heidelberg :
_bSpringer Berlin Heidelberg :
_bImprint: Springer,
_c2019.
300 _aXI, 398 p. 1349 illus.
_bonline resource.
336 _atext
_btxt
_2rdacontent
337 _acomputer
_bc
_2rdamedia
338 _aonline resource
_bcr
_2rdacarrier
347 _atext file
_bPDF
_2rda
490 1 _aTheoretical Computer Science and General Issues,
_x2512-2029 ;
_v11880
505 0 _aComplexity Theory and Non-determinism -- Parameterized Complexity Theory -- Fpt-Reducibility to SAT -- The Need for a New Completeness Theory -- A New Completeness Theory -- Fpt-algorithms with Access to a SAT Oracle -- Problems in Knowledge Representation and Reasoning -- Model Checking for Temporal Logics -- Problems Related to Propositional Satisfiability -- Problems in Judgment Aggregation -- Planning Problems -- Graph Problems -- Relation to Other Topics in Complexity Theory -- Subexponential-Time Reductions -- Non-Uniform Parameterized Complexity -- Open Problems and Future Research Directions -- Conclusion -- Compendium of Parameterized Problems -- Generalization to Higher Levels of the Polynomial Hierarchy.
520 _aThe book presents the co-recipient of the E.W. Beth Dissertation Prize 2017 for outstanding dissertations in the fields of logic, language, and information. This work extends the theory of parameterized complexity to higher levels of the Polynomial Hierarchy (PH). For problems at higher levels of the PH, a promising solving approach is to develop fixed-parameter tractable reductions to SAT, and to subsequently use a SAT solving algorithm to solve the problem. In this dissertation, a theoretical toolbox is developed that can be used to classify in which cases this is possible. The use of this toolbox is illustrated by applying it to analyze a wide range of problems from various areas of computer science and artificial intelligence.
650 0 _aMathematical logic.
650 0 _aMachine theory.
650 1 4 _aMathematical Logic and Foundations.
650 2 4 _aFormal Languages and Automata Theory.
710 2 _aSpringerLink (Online service)
773 0 _tSpringer Nature eBook
776 0 8 _iPrinted edition:
_z9783662606698
776 0 8 _iPrinted edition:
_z9783662606711
830 0 _aTheoretical Computer Science and General Issues,
_x2512-2029 ;
_v11880
856 4 0 _uhttps://doi.org/10.1007/978-3-662-60670-4
912 _aZDB-2-SCS
912 _aZDB-2-SXCS
912 _aZDB-2-LNC
942 _cSPRINGER
999 _c173475
_d173475