[Back]

R. de Haan, S. Szeider:
"Machine Characterizations for Parameterized Complexity Classes Beyond Para-NP";
Talk: International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM), Pec pod Snezkou, Czech Republic; 2015-01-24 - 2015-01-29; in: "41st International Conference on Current Trends in Theory and Practice of Computer Science - SOFSEM 2015", G. Italiano, T. Margaria, J. Pokorný, J. Quisquater, R. Wattenhofer (ed.); LNCS, 8939 (2015), ISBN: 978-3-662-46077-1; 217 - 229.

Due to the remarkable power of modern SAT solvers, one can efficiently solve NP-complete problems in many practical settings by encoding them into SAT. However, many important problems in various areas of computer science lie beyond NP, and thus we cannot hope for polynomial-time encodings into SAT. Recent research proposed the use of fixed-parameter tractable (fpt) reductions to provide efficient SAT encodings for these harder problems. The parameterized complexity classes ∃k∀* and ∀k∃* provide strong theoretical evidence that certain parameterized problems are not fpt-reducible to SAT. Originally, these complexity classes were defined via weighted satisfiability problems for quantified Boolean formulas, extending the general idea for the canonical problems for the Weft Hierarchy.
In this paper, we provide alternative characterizations of ∃k∀* and ∀k∃* in terms of first-order logic model checking problems and problems involving alternating Turing machines with appropriate time bounds and bounds on the number of alternations. We also identify parameterized Halting Problems for alternating Turing machines that are complete for these classes.

The alternative characterizations provide evidence for the robustness of the new complexity classes and extend the toolbox for establishing membership results. As an illustration, we consider various parameterizations of the 3-coloring extension problem.

parameterized complexity classes beyond para-np

http://dx.doi.org/10.1007/978-3-662-46078-8