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].
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:
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
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).