User contributions
Jump to navigation
Jump to search
- 16:36, 4 December 2024 diff hist +222 Complexity Zoo:S →SPP: Stoic PP: fix the definition as per [FFK94]
- 17:20, 6 November 2024 diff hist +25 Template:CZ-Q also missing
- 17:18, 6 November 2024 diff hist +91 Template:CZ-Q missing cats
- 17:17, 6 November 2024 diff hist -2 Complexity Zoo:Q →QNC0/🐱: Quantum NC0 With Polynomial-Size Quantum Advice: fix duplicate id
- 17:03, 6 November 2024 diff hist +31 Template:CZ-S + SIZE
- 17:01, 6 November 2024 diff hist +26 m Complexity Zoo:C →CSIZE(f(n)): Circuit Size f(n): link current
- 17:00, 6 November 2024 diff hist +131 Complexity Zoo:S + SIZE
- 16:54, 6 November 2024 diff hist +32 Complexity Zoo:C →CSIZE(f(n)): Circuit Size f(n): more common notation, IME
- 16:53, 6 November 2024 diff hist +77 Template:CZ-C add missing classes, and reorder to match the main article current
- 16:44, 6 November 2024 diff hist +4 Complexity Zoo:T →TC: Threshold Circuits: This exactly defines majority, not more general threshold gates
- 16:41, 6 November 2024 diff hist -12 m Complexity Zoo:T →TC1: Log-depth Threshold Circuits
- 16:39, 6 November 2024 diff hist +99 Template:CZ-T add a bunch of missing clases current
- 08:16, 6 November 2024 diff hist 0 Template:CZ-T
- 08:15, 6 November 2024 diff hist +49 Complexity Zoo:E →ELEMENTARY: Iterated Exponential Time: fix a confusing description current
- 08:15, 6 November 2024 diff hist 0 Complexity Zoo:T →Tower: Iterated Exponential Time: It's actually written in all caps in the source, as is common for most complexity classes
- 08:12, 6 November 2024 diff hist +18 Complexity Zoo:T →Tower: Tetrational Time: "Tetration" is a rarely used word. Use a more common description
- 08:43, 29 May 2024 diff hist +158 Complexity Zoo:P →PP: Probabilistic Polynomial-Time
- 08:37, 29 May 2024 diff hist +178 Complexity Zoo References →F
- 06:36, 29 May 2024 diff hist +35 Complexity Zoo:P →P#P: P With #P Oracle
- 06:32, 29 May 2024 diff hist +27 Complexity Zoo:P →P#P[1]: P With Single Query To #P Oracle
- 06:31, 29 May 2024 diff hist +37 Complexity Zoo:M →MP: Middle-Bit P
- 06:28, 29 May 2024 diff hist +103 Complexity Zoo:P →P#P[1]: P With Single Query To #P Oracle
- 06:25, 29 May 2024 diff hist +62 Complexity Zoo:M →MP: Middle-Bit P
- 12:19, 3 May 2024 diff hist +211 Complexity Zoo:O →O2P: Second Level of the Oblivious Symmetric Hierarchy
- 09:33, 2 May 2024 diff hist +3 Complexity Zoo:S →S2E: Second Level of the Symmetric Linear Exponent Hierarchy: The argument gives \Omega(2^n/n), not the maximal possible circuit size.
- 10:48, 4 July 2023 diff hist +89 Complexity Zoo:P →PP: Probabilistic Polynomial-Time: reorder to put related facts together
- 11:40, 22 June 2023 diff hist +64 Complexity Zoo:List of Hierarchies
- 11:36, 22 June 2023 diff hist -9 Complexity Zoo:M →MP: Middle-Bit P
- 11:35, 22 June 2023 diff hist +35 Complexity Zoo:A →AmpMP: Amplifiable MP
- 11:34, 22 June 2023 diff hist +1 Complexity Zoo:M →ModPH: Modular Counting Hierarchy
- 11:33, 22 June 2023 diff hist +21 Complexity Zoo:M →ModkP: Mod-k Polynomial-Time
- 11:32, 22 June 2023 diff hist +22 Complexity Zoo:M →ModPH: Modular Counting Hierarchy
- 11:30, 22 June 2023 diff hist +815 Complexity Zoo:M
- 11:30, 22 June 2023 diff hist +27 Template:CZ-M current
- 11:23, 22 June 2023 diff hist +1 Complexity Zoo References →B
- 11:22, 22 June 2023 diff hist +168 Complexity Zoo References →B
- 11:06, 22 June 2023 diff hist +37 Complexity Zoo:E →∃R: Existential theory of the reals
- 11:05, 22 June 2023 diff hist +189 Complexity Zoo References →S
- 11:01, 22 June 2023 diff hist +32 Template:CZ-E current
- 11:00, 22 June 2023 diff hist +5 Complexity Zoo:E →∃R: Existential theory of the reals
- 10:54, 22 June 2023 diff hist +130 Complexity Zoo:E →∃Reals : Problems in ETR: improve description
- 18:54, 6 July 2021 diff hist +160 Complexity Zoo:O →O2P: Second Level of the Oblivious Symmetric Hierarchy: mention inclusion in P/poly
- 18:51, 6 July 2021 diff hist +47 Complexity Zoo:P →P/poly: Nonuniform Polynomial-Time: improve the collapse from S2P to O2P
- 09:11, 19 April 2021 diff hist -11 m Complexity Zoo:A →Almost-PSPACE: Languages Almost Surely in PSPACEA: fix broken entities
- 19:24, 5 July 2019 diff hist +85 Complexity Zoo References →J: published reference
- 19:19, 5 July 2019 diff hist +39 Complexity Zoo:P →PNP[log^2]: P With Log2 NP Queries: correct statement from the CS92 paper
- 19:10, 5 July 2019 diff hist +73 Complexity Zoo:P →PNP[log]: P With Log NP Queries: a common name
- 19:07, 5 July 2019 diff hist +42 Complexity Zoo:A →AC0: Unbounded Fanin Constant-Depth Circuits: Restore a deleted correct claim. (Only the reference to AL was wrong.)
- 11:08, 1 April 2012 diff hist +16 N Template:CZ-K Created page with '[[{{{1|}}}#k|K]]'
- 11:06, 1 April 2012 diff hist +571 N Complexity Zoo:K No class starting with K? Must fix that.