Parameterized complexity: Difference between revisions

Revision as of 15:08, 14 May 2019

Revision as of 14:14, 23 May 2019

Line 76:

=== XP ===

'''XP''' is the class of parameterized problems that can be solved in time <math>n^{f(k)}</math> for some computable function {{mvar|f}}. These problems are called [[slicewise]] polynomial, in the sense that each "slice" of fixed k has a polynomial algorithm, although possibly with a different exponent for each k. Compare this with FPT, which merely allows a different constant prefactor for each value of k. XP contains FPT, and it is believedknown that this containment is strict by diagonalization.

{{Expand section|date=April 2019}}