Class Description

XPuniform: 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:

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 XPuniform

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 XPuniform.

Strictly contains FPT (by diagonalization).

More about...