Class Description

SPARSE: Sparse Languages

The class of decision problems for which the number of 'yes' instances of size n is upper-bounded by a polynomial in n. If SPARSE intersects NPC then P = NP [Mah82].

Contains TALLY.

Linked From

coSPARSE: Complement of SPARSE

More about...


NONE: The Empty Class

The class that does not contain any languages. (It might not surprise you that I put this one in at the suggestion of a mathematician...)

Is the opposite of ALL, but does not equal the complement coALL = ALL.

Is closed under polynomial-time Turing reductions :-).

Equals SPARSEcoSPARSE and TALLYcoTALLY.

More about...


TALLY: Tally Languages

The class of decision problems for which every 'yes' instance has the form 0n (i.e. inputs are encoded in unary). If TALLY intersects NPC then P = NP [Mah82].

Contained in SPARSE.

More about...