Class Description

XP_uniform: Uniform XP

Same as XP except that the algorithm used must be the same for each k (though it can take k as input).

Defined in [DF99].

Linked From

EPTAS: Efficient Polynomial-Time Approximation Scheme

The class of optimization problems such that, given an instance of length n, we can find a solution within a factor 1+ε of the optimum in time f(ε)p(n), where p is a polynomial and f is arbitrary.

Contains FPTAS and is contained in PTAS.

Defined in [CT97], where the following was also shown:

• If FPT = XP_uniform then EPTAS = PTAS.
• If EPTAS = PTAS then FPT = W[P].
• If FPT is strictly contained in W[1], then there is a natural problem that is in PTAS but not in EPTAS. (See [CT97] for the statement of the problem, since it's not that natural.)

More about...

SP: Semi-Efficient Parallel

The class of problems in P for which the best parallel algorithm (using a polynomial number of processors) is faster than the best serial algorithm by a factor of Ω(n^ε) for some ε>0.

Defined in [KRS90].

SP is also an alternate name for XP_uniform

More about...

XP: Fixed-Parameter Tractable for Each Parameter

The class of decision problems of the form (x,k) (k a parameter) that are solvable in time O(|x|^f(k)) for some function f. The algorithm used may depend on k.

Defined in [DF99].

Contains XP_uniform.

Strictly contains FPT (by diagonalization).

More about...