[Back]


Publications in Scientific Journals:

R. de Haan, S. Szeider:
"Parameterized complexity classes beyond para-NP";
Journal of Computer and System Sciences, 87 (2017), 16 - 57.



English abstract:
Today´s propositional satisfiability (SAT) solvers are extremely
powerful and can be used as an efficient back-end for solving
NP-complete problems. However, many fundamental problems in logic, in
knowledge representation and reasoning, and in artificial intelligence
are located at the second level of the Polynomial Hierarchy or even
higher, and hence for these problems polynomial-time transformations
to SAT are not possible, unless the hierarchy collapses. Recent
research shows that in certain cases one can break through these
complexity barriers by fixed-parameter tractable (fpt) reductions to
SAT which exploit structural aspects of problem instances in terms of
problem parameters. These reductions are more powerful because their
running times can grow superpolynomially in the problem parameters. In
this paper we develop a general theoretical framework that supports
the classification of parameterized problems on whether they admit such
an fpt-reduction to SAT or not.


"Official" electronic version of the publication (accessed through its Digital Object Identifier - DOI)
http://dx.doi.org/10.1016/j.jcss.2017.02.002

Electronic version of the publication:
http://www.sciencedirect.com/science/article/pii/S0022000017300089?via%3Dihub


Created from the Publication Database of the Vienna University of Technology.