Content deleted Content added
m →References: Task 16: replaced (1×) / removed (0×) deprecated |dead-url= and |deadurl= with |url-status=; |
No edit summary |
||
Line 79:
{{Expand section|date=April 2019}}
=== para-NP ===
'''para-NP''' is the class of parameterized problems that can be solved by a [[Nondeterministic algorithm|nondeterministic algorithm]] in time <math>f(k) \cdot |x|^{O(1)}</math> for some computable function <math>f</math>. It is known that <math>\text{FPT}=\text{para-NP}</math> if and only if <math>\text{P}=\text{NP}</math>. {{sfnp|Flum|Grohe|page=39}}
A problem is '''para-NP-hard''' if it is <math>\text{NP}</math>-hard already for a constant value of the parameter. That is, there is a "slice" of fixed <math>k</math> that is <math>\text{NP}</math>-hard. A parameterized problem that is <math>\text{para-NP}</math>-hard cannot belong to the class <math>\text{XP}</math>, unless <math>\text{P}=\text{NP}</math>. A classic example of a <math>\text{para-NP}</math>-hard parameterized problem is [[Graph coloring|graph coloring]], parameterized by the number <math>k</math> of colors, which is already <math>\text{NP}</math>-hard for <math>k=3</math> (see [[Graph coloring#Computational_complexity]]).
=== A hierarchy ===
| |||