Class Description

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

Linked From

No class.