Class Description

TALLY: Tally Languages

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

Contained in SPARSE.

Linked From

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 SPARSE ∩ coSPARSE and TALLY ∩ coTALLY.

More about...

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.

More about...

YP: Your Polynomial-Time or Yaroslav-Percival

The class of decision problems for which there exists a polynomial-time machine M such that:

• For all input sizes n, there exists a polynomial-size advice string s_n such that M(x,s_n) outputs the correct answer for all inputs x of size n.
• For all inputs x and advice strings s, M(x,s) outputs either the correct answer or "I don't know."

Defined in a recent post of the blog Shtetl-Optimized. See there for an explanation of the class's name.

Contains ZPP by the same argument that places BPP in P/poly.

Also contains P with TALLY ∩ NP ∩ coNP oracle.

Is contained in NP ∩ coNP and YPP.

Is equal to ONP ∩ coONP.

More about...