Parameterized complexity classes beyond para-NP

作者：

Highlights：

• We develop parameterized complexity classes that can be used to provide evidence that problems are not fpt-reducible to SAT.

• We show that these classes can be characterized by means of several fundamental concepts from theoretical computer science.

• We show how these classes can be employed in the computational complexity analysis of many natural parameterized problems.

• We give evidence that these classes are different from parameterized complexity classes that are known from the literature.

• We provide a compendium of natural parameterized problems that are complete for the new parameterized complexity classes.

摘要

•We develop parameterized complexity classes that can be used to provide evidence that problems are not fpt-reducible to SAT.•We show that these classes can be characterized by means of several fundamental concepts from theoretical computer science.•We show how these classes can be employed in the computational complexity analysis of many natural parameterized problems.•We give evidence that these classes are different from parameterized complexity classes that are known from the literature.•We provide a compendium of natural parameterized problems that are complete for the new parameterized complexity classes.

论文关键词：Parameterized complexity,Fpt-reductions,Polynomial hierarchy,Weft-hierarchy

论文评审过程：Received 25 November 2014, Revised 13 December 2016, Accepted 1 February 2017, Available online 11 April 2017, Version of Record 11 April 2017.

论文官网地址：https://doi.org/10.1016/j.jcss.2017.02.002