{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,5]],"date-time":"2026-07-05T04:27:05Z","timestamp":1783225625580,"version":"3.54.6"},"reference-count":60,"publisher":"MDPI AG","issue":"9","license":[{"start":{"date-parts":[[2019,9,9]],"date-time":"2019-09-09T00:00:00Z","timestamp":1567987200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["239962"],"award-info":[{"award-number":["239962"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002428","name":"Austrian Science Fund","doi-asserted-by":"publisher","award":["P26200"],"award-info":[{"award-number":["P26200"]}],"id":[{"id":"10.13039\/501100002428","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>We present a list of parameterized problems together with a complexity classification of whether they allow a fixed-parameter tractable reduction to SAT or not. These problems are parameterized versions of problems whose complexity lies at the second level of the Polynomial Hierarchy or higher.<\/jats:p>","DOI":"10.3390\/a12090188","type":"journal-article","created":{"date-parts":[[2019,9,9]],"date-time":"2019-09-09T11:26:17Z","timestamp":1568028377000},"page":"188","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["A Compendium of Parameterized Problems at Higher Levels of the Polynomial Hierarchy"],"prefix":"10.3390","volume":"12","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2023-0586","authenticated-orcid":false,"given":"Ronald","family":"de Haan","sequence":"first","affiliation":[{"name":"Institute for Logic, Language and Computation (ILLC), University of Amsterdam, 1000\u20131183 Amsterdam, The Netherlands"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8994-1656","authenticated-orcid":false,"given":"Stefan","family":"Szeider","sequence":"additional","affiliation":[{"name":"Algorithms and Complexity Group, Institute for Logic and Computation, Faculty of Informatics, Technische Universit\u00e4t Wien, 1040 Vienna, Austria"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"1968","published-online":{"date-parts":[[2019,9,9]]},"reference":[{"key":"ref_1","first-page":"5","article-title":"Boolean satisfiability: Theory and engineering","volume":"57","author":"Vardi","year":"2014","journal-title":"Commun. ACM"},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0304-3975(76)90061-X","article-title":"The polynomial-time hierarchy","volume":"3","author":"Stockmeyer","year":"1976","journal-title":"Theor. Comput. Sci."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1016\/0304-3975(76)90062-1","article-title":"Complete Sets and the Polynomial-Time Hierarchy","volume":"3","author":"Wrathall","year":"1976","journal-title":"Theor. Comput. Sci."},{"key":"ref_4","unstructured":"Chen, H. (2004, January 22\u201327). Quantified Constraint Satisfaction and Bounded Treewidth. Proceedings of the 16th European Conference on Artificial Intelligence (ECAI 2004), Valencia, Spain."},{"key":"ref_5","unstructured":"Feder, T., and Kolaitis, P.G. (2006). Closures and dichotomies for quantified constraints. Electronic Colloquium on Computational Complexity (ECCC), Weizmann Institute of Science. Technical Report TR06-160."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1007\/978-3-319-09284-3_8","article-title":"Fixed-parameter tractable reductions to SAT","volume":"Volume 8561","author":"Egly","year":"2014","journal-title":"Proceedings of the 17th International Symposium on the Theory and Applications of Satisfiability Testing (SAT 2014)"},{"key":"ref_7","unstructured":"De Haan, R. (2016). Parameterized Complexity in the Polynomial Hierarchy. [Ph.D. Thesis, Technische Universit\u00e4t Wien]."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"16","DOI":"10.1016\/j.jcss.2017.02.002","article-title":"Parameterized complexity classes beyond para-NP","volume":"87","author":"Szeider","year":"2017","journal-title":"J. Comput. Syst. Sci."},{"key":"ref_9","first-page":"32","article-title":"Completeness in the Polynomial-Time hierarchy: A Compendium","volume":"33","author":"Schaefer","year":"2002","journal-title":"SIGACT News"},{"key":"ref_10","unstructured":"Cesati, M. (2019, September 04). Compendium of Parameterized Problems. Available online: http:\/\/cesati.sprg.uniroma2.it\/research\/compendium\/."},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Arora, S., and Barak, B. (2009). Computational Complexity\u2014A Modern Approach, Cambridge University Press.","DOI":"10.1017\/CBO9780511804090"},{"key":"ref_12","unstructured":"Papadimitriou, C.H. (1994). Computational Complexity, Addison-Wesley."},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Meyer, A.R., and Stockmeyer, L.J. (1972, January 25\u201327). The Equivalence Problem for Regular Expressions with Squaring Requires Exponential Space. Proceedings of the 13th Annual Symposium on Switching & Automata Theory (SWAT), College Park, MD, USA.","DOI":"10.1109\/SWAT.1972.29"},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"299","DOI":"10.1016\/0022-0000(89)90025-1","article-title":"The strong exponential hierarchy collapses","volume":"39","author":"Hemachandra","year":"1989","journal-title":"J. Comput. Syst. Sci."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"86","DOI":"10.1016\/0890-5401(91)90075-D","article-title":"On truth-table reducibility to SAT","volume":"91","author":"Buss","year":"1991","journal-title":"Inf. Comput."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"1232","DOI":"10.1137\/0217078","article-title":"The Boolean Hierarchy I: Structural Properties","volume":"17","author":"Cai","year":"1988","journal-title":"SIAM J. Comput."},{"key":"ref_17","first-page":"169","article-title":"The Boolean Hierarchy and the Polynomial Hierarchy: A Closer Connection","volume":"25","author":"Chang","year":"1993","journal-title":"SIAM J. Comput."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"1263","DOI":"10.1137\/0217080","article-title":"The Polynomial Time Hierarchy Collapses if the Boolean Hierarchy Collapses","volume":"17","author":"Kadin","year":"1988","journal-title":"SIAM J. Comput."},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Cygan, M., Fomin, F.V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., and Saurabh, S. (2015). Parameterized Algorithms, Springer.","DOI":"10.1007\/978-3-319-21275-3"},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Downey, R.G., and Fellows, M.R. (1999). Parameterized Complexity. Monographs in Computer Science, Springer.","DOI":"10.1007\/978-1-4612-0515-9"},{"key":"ref_21","doi-asserted-by":"crossref","unstructured":"Downey, R.G., and Fellows, M.R. (2013). Texts in Computer Science. Fundamentals of Parameterized Complexity, Springer.","DOI":"10.1007\/978-1-4471-5559-1"},{"key":"ref_22","unstructured":"Flum, J., and Grohe, M. (2006). Parameterized Complexity Theory. Texts in Theoretical Computer Science. An EATCS Series, Springer."},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Niedermeier, R. (2006). Invitation to Fixed-Parameter Algorithms. Oxford Lecture Series in Mathematics and Its Applications, Oxford University Press.","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001"},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"291","DOI":"10.1016\/S0890-5401(03)00161-5","article-title":"Describing parameterized complexity classes","volume":"187","author":"Flum","year":"2003","journal-title":"Inf. Comput."},{"key":"ref_25","doi-asserted-by":"crossref","unstructured":"Cook, S.A. (1971, January 3\u20135). The Complexity of Theorem-Proving Procedures. Proceedings of the Third Annual ACM Symposium on Theory of Computing, Shaker Heights, OH, USA.","DOI":"10.1145\/800157.805047"},{"key":"ref_26","first-page":"265","article-title":"Universal sequential search problems","volume":"9","author":"Levin","year":"1973","journal-title":"Probl. Inf. Transm."},{"key":"ref_27","unstructured":"Biere, A., Heule, M., van Maaren, H., and Walsh, T. (2009). CNF Encodings. Handbook of Satisfiability, IOS Press."},{"key":"ref_28","unstructured":"Endriss, U., De Haan, R., and Szeider, S. (2015, January 4\u20138). Parameterized Complexity Results for Agenda Safety in Judgment Aggregation. Proceedings of the 14th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2015), Istanbul, Turkey."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"7:1","DOI":"10.1145\/2818646","article-title":"Backdoors to Normality for Disjunctive Logic Programs","volume":"17","author":"Fichte","year":"2015","journal-title":"ACM Trans. Comput. Log."},{"key":"ref_30","unstructured":"Baral, C., De Giacomo, G., and Eiter, T. (2014, January 20\u201324). The Parameterized Complexity of Reasoning Problems Beyond NP. Proceedings of the Fourteenth International Conference on the Principles of Knowledge Representation and Reasoning (KR 2014), Vienna, Austria."},{"key":"ref_31","unstructured":"Rossi, F. (2013, January 3\u20139). Backdoors to Abduction. Proceedings of the 23rd International Joint Conference on Artificial Intelligence (IJCAI 2013), Beijing, China."},{"key":"ref_32","first-page":"23","article-title":"Complexity of a Derivation in the Propositional Calculus","volume":"8","author":"Tseitin","year":"1968","journal-title":"Zap. Nauchn. Sem. Leningrad Otd. Mat. Inst. Akad. Nauk SSSR"},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"97","DOI":"10.3233\/AIC-2012-0523","article-title":"Towards efficient MUS extraction","volume":"25","author":"Belov","year":"2012","journal-title":"AI Commun."},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1016\/j.artint.2013.10.001","article-title":"Complexity-sensitive decision procedures for abstract argumentation","volume":"206","author":"Wallner","year":"2014","journal-title":"Artif. Intell."},{"key":"ref_35","first-page":"592","article-title":"Minimal Sets over Monotone Predicates in Boolean Formulae","volume":"Volume 8044","author":"Sharygina","year":"2013","journal-title":"Proceedings of the 25th International Conference Computer Aided Verification (CAV 2013)"},{"key":"ref_36","unstructured":"De Haan, R., and Szeider, S. (2016, January 25\u201329). Parameterized Complexity Results for Symbolic Model Checking of Temporal Logics. Proceedings of the Fifteenth International Conference on the Principles of Knowledge Representation and Reasoning (KR 2016), Cape Town, South Africa."},{"key":"ref_37","unstructured":"Endriss, U., De Haan, R., and Szeider, S. (2014, January 4\u20138). Parameterized Complexity Results for Agenda Safety in Judgment Aggregation. Proceedings of the 5th International Workshop on Computational Social Choice (COMSOC-2014), Istanbul, Turkey."},{"key":"ref_38","unstructured":"De Haan, R. (2015). An Overview of Non-Uniform Parameterized Complexity. Electronic Colloquium on Computational Complexity (ECCC), Weizmann Institute of Science. Technical Report TR15-130."},{"key":"ref_39","unstructured":"De Haan, R., Kronegger, M., and Pfandler, A. (2015, January 25\u201331). Fixed-parameter Tractable Reductions to SAT for Planning. Proceedings of the 24th International Joint Conference on Artificial Intelligence (IJCAI 2015), Buenos Aires, Argentina."},{"key":"ref_40","unstructured":"De Haan, R., and Szeider, S. (2014). Compendium of Parameterized Problems at Higher Levels of the Polynomial Hierarchy. Electronic Colloquium on Computational Complexity (ECCC), Weizmann Institute of Science. Technical Report TR14\u2013143."},{"key":"ref_41","doi-asserted-by":"crossref","unstructured":"De Haan, R., and Szeider, S. (2015, January 24\u201329). Machine Characterizations for Parameterized Complexity Classes beyond para-NP. Proceedings of the 41st Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2015), Pec pod Sn\u011b\u017ekou, Czech Republic.","DOI":"10.1007\/978-3-662-46078-8_18"},{"key":"ref_42","doi-asserted-by":"crossref","unstructured":"Kloks, T. (1994). Treewidth: Computations and Approximations, Springer.","DOI":"10.1007\/BFb0045375"},{"key":"ref_43","doi-asserted-by":"crossref","first-page":"1305","DOI":"10.1137\/S0097539793251219","article-title":"A linear-time algorithm for finding tree-decompositions of small treewidth","volume":"25","author":"Bodlaender","year":"1996","journal-title":"SIAM J. Comput."},{"key":"ref_44","first-page":"187","article-title":"QUBOS: Deciding Quantified Boolean Logic Using Propositional Satisfiability Solvers","volume":"Volume 2517","author":"Aagaard","year":"2002","journal-title":"Proceedings of the 4th International Conference on Formal Methods in Computer-Aided Design (FMCAD 2002)"},{"key":"ref_45","unstructured":"Biere, A. (2004, January 10\u201313). Resolve and Expand. Proceedings of the Seventh International Conference on Theory and Applications of Satisfiability Testing (SAT 2004), Vancouver, BC, Canada."},{"key":"ref_46","unstructured":"Umans, C. (2000). Approximability and Completeness in the Polynomial Hierarchy. [Ph.D. Thesis, University of California]."},{"key":"ref_47","first-page":"1502","article-title":"Parameterized Complexity Results for the Kemeny Rule in Judgment Aggregation","volume":"Volume 285","author":"Kaminka","year":"2016","journal-title":"Proceedings of the 22nd European Conference on Artificial Intelligence (ECAI 2016)"},{"key":"ref_48","doi-asserted-by":"crossref","first-page":"92","DOI":"10.1145\/2043174.2043195","article-title":"Answer set programming at a glance","volume":"54","author":"Brewka","year":"2011","journal-title":"Commun. ACM"},{"key":"ref_49","doi-asserted-by":"crossref","unstructured":"Marek, V.W., and Truszczynski, M. (1999). Stable models and an alternative logic programming paradigm. The Logic Programming Paradigm: A 25-Year Perspective, Springer.","DOI":"10.1007\/978-3-642-60085-2_17"},{"key":"ref_50","doi-asserted-by":"crossref","first-page":"365","DOI":"10.1007\/BF03037169","article-title":"Classical Negation in Logic Programs and Disjunctive Databases","volume":"9","author":"Gelfond","year":"1991","journal-title":"New Gener. Comput."},{"key":"ref_51","doi-asserted-by":"crossref","first-page":"42","DOI":"10.1016\/j.artint.2012.07.006","article-title":"On minimal constraint networks","volume":"191\u2013192","author":"Gottlob","year":"2012","journal-title":"Artif. Intell."},{"key":"ref_52","unstructured":"Rossi, F. (2013, January 3\u20139). Robust Constraint Satisfaction and Local Hidden Variables in Quantum Mechanics. Proceedings of the 23rd International Joint Conference on Artificial Intelligence (IJCAI 2013), Beijing, China."},{"key":"ref_53","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1145\/200836.200838","article-title":"The complexity of logic-based abduction","volume":"42","author":"Eiter","year":"1995","journal-title":"J. ACM"},{"key":"ref_54","doi-asserted-by":"crossref","first-page":"660","DOI":"10.1006\/jcss.1999.1691","article-title":"The Closure of Monadic NP","volume":"60","author":"Ajtai","year":"2000","journal-title":"J. Comput. Syst. Sci."},{"key":"ref_55","unstructured":"Baier, C., and Katoen, J.P. (2008). Principles of Model Checking, MIT Press."},{"key":"ref_56","unstructured":"Clarke, E.M., Grumberg, O., and Peled, D.A. (1999). Model Checking, MIT Press."},{"key":"ref_57","doi-asserted-by":"crossref","first-page":"481","DOI":"10.1613\/jair.3708","article-title":"Complexity of Judgment Aggregation","volume":"45","author":"Endriss","year":"2012","journal-title":"J. Artif. Intell. Res."},{"key":"ref_58","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1016\/j.jet.2006.04.008","article-title":"The structure of strategy-proof social choice\u2014Part I: General characterization and possibility results on median spaces","volume":"135","author":"Nehring","year":"2007","journal-title":"J. Econ. Theory"},{"key":"ref_59","doi-asserted-by":"crossref","first-page":"625","DOI":"10.1111\/j.1467-8640.1995.tb00052.x","article-title":"Complexity Results for SAS+ Planning","volume":"11","author":"Nebel","year":"1995","journal-title":"Comput. Intell."},{"key":"ref_60","unstructured":"Pednault, E.P.D. (1989, January 15\u201318). ADL: Exploring the Middle Ground Between STRIPS and the Situation Calculus. Proceedings of the 1st International Conference on Principles of Knowledge Representation and Reasoning (KR 1989), Toronto, ON, Canada."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/12\/9\/188\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T13:18:09Z","timestamp":1760188689000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/12\/9\/188"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,9,9]]},"references-count":60,"journal-issue":{"issue":"9","published-online":{"date-parts":[[2019,9]]}},"alternative-id":["a12090188"],"URL":"https:\/\/doi.org\/10.3390\/a12090188","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,9,9]]}}}