Parameterized complexity: Difference between revisions

Revision as of 17:11, 30 October 2021

Revision as of 15:41, 6 February 2022

Line 81:

=== para-NP ===

'''para-NP''' is the class of parameterized problems that can be solved by a [[nondeterministic algorithm]] in time <math>f(k) \cdot |x|^{O(1)}</math> for some computable function {{mvar|f}}. It is known that <math>\textsf{FPT}=\textsf{para-NP}</math> if and only if <math>\textsf{P}=\textsf{NP}</math>. {{sfnp|Flum|Grohe|2006|page=39}}

A problem is '''para-NP-hard''' if it is <math>\textsf{NP}</math>-hard already for a constant value of the parameter. That is, there is a "slice" of fixed {{mvar|k}} that is <math>\textsf{NP}</math>-hard. A parameterized problem that is <math>\textsf{para-NP}</math>-hard cannot belong to the class <math>\textsf{XP}</math>, unless <math>\textsf{P}=\textsf{NP}</math>. A classic example of a <math>\textsf{para-NP}</math>-hard parameterized problem is [[graph coloring]], parameterized by the number {{mvar|k}} of colors, which is already <math>\textsf{NP}</math>-hard for <math>k=3</math> (see [[Graph coloring#Computational complexity]]).