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
No class.