✳flâneur — a map of the web's best reading

Complexity Zoo:T - Complexity Zoo

complexityzoo.net · 1,394 words · saved by 1 readers

Complexity classes by letter: Symbols - A - B - C - D - E - F - G - H - I - J - K - L - M - N - O - P - Q - R - S - T - U - V - W - X - Y - Z Lists of related classes: Communication Complexity - Hierarchies - Nonuniform TALLY - TC - TC0 - TC0(FOLL) - TC1 - TFNP - Θ2P - TI - TOWER - TreeBQP - TREE-REGULAR 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. TCi is the class of decision problems solvable by polynomial-size, depth 𝑂 ( log 𝑖 ⁡ 𝑛 ) circuits with unbounded fanin AND, OR, and majority (MAJ) gates. A majority gate returns 1 if at least half of its inputs are 1, and 0 otherwise. Other gates that can be used in place of majority (up to polynomial size equivalence) are threshold gates (THR) and MODpn, where pn is the nth prime. A uniformity requirement is sometimes also placed. Each TCi contains ACi (in fact ACCi) and is contained in NCi+1. Thus NC =

Complexity Zoo:T - Complexity Zoo Complexity Zoo:T From Complexity Zoo Jump to navigation Jump to search Back to the Main Zoo - Complexity Garden - Zoo Glossary - Zoo References Complexity classes by letter: Symbols - A - B - C - D - E - F - G - H - I - J - K - L - M - N - O - P - Q - R - S - T - U - V - W - X - Y - Z Lists of related classes: Communication Complexity - Hierarchies - Nonuniform TALLY - TC - TC 0 - TC 0 (FOLL) - TC 1 - TFNP - Θ 2 P - TI - TOWER - TreeBQP - TREE-REGULAR TALLY : Tally Languages The class of decision problems for which every 'yes' instance has the form 0 n (i

Explore this link on the map →

related reading