000 03479nam a22005415i 4500
001 978-3-662-60670-4
003 DE-He213
005 20240730165616.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
_989796
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.
_92258
650 0 _aMachine theory.
_989797
650 1 4 _aMathematical Logic and Foundations.
_934712
650 2 4 _aFormal Languages and Automata Theory.
_989798
710 2 _aSpringerLink (Online service)
_989799
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
_989800
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 _cELN
999 _c86425
_d86425