Identities in Computational Complexity

Guest post by Josh Grochow

On the birdsite, Jay Cummings tweeted:

TOP 5 IDENTITIES OF ALL TIME
5. You
4. Can't
3. Rank
2. Identities
1. e^iπ + 1 = 0

— Jay Cummings (@LongFormMath) February 8, 2023

And it got me thinking about identities in computational complexity. At first I thought: how many could there be? 10? After some thought and with some help, there turn out to be quite a few more than that, and I think they make a pretty good list!

Rules/comments on the list:

• Some are relatively simple alternative characterizations, such as the various definitions of PH; most are pretty nontrivial theorems.
• I didn't include existentially quantified oracle results (such as "there exists A such that P^A=NP^A"), despite them being some of my favorite results, because there'd be waaaay too many of those. Probably thousands? Ask Lance. In some circles he's known as the "oracle oracle" - as in, he's who you go ask if you want to know if a certain oracle exists. I did include identities involving oracles where one side of the identity didn't have an oracle, such as EXP=NP^R_Kt or AlmostP=BPP (AlmostP is the class of languages L such that {A : L is in P^A} has measure 1).
• I also didn't include some important conditional equalities, such as "EXP in P/poly iff EXP=MA" or "NP in BPP iff NP=RP". I guess it's not really an "identity" if it's conditional. Games are only fun if the rules are at least a little constraining!
• There are some surprising containments that either aren't equalities, or aren't known to be equalities, and I didn't include those either, despite some of them being very important. For example, BPP in Σ₂P, other depth reduction results (such as the chasms at depth 4 and 3), and Beigel-Tarui/Yao.

One could teach a class based on a list like this and cover a lot of good ground, but I think it'd be sad to leave out any lower bounds. Actually, by my estimate, if you were teaching from "scratch" (say, starting after an undergrad algorithms class), this list, and all its implied prerequisite material, is already probably the equivalent of about 3-4 semester-long classes!

What other complexity identities did I miss?

Finally, without further ado, a list of (some) identities in computational complexity:

RP∩coRP=ZPP

CLS=PPAD∩PLS [from Paul Goldberg @paulwgoldberg]

quasi-poly Frege =quasi-poly noncommutative formula IPS

Space classes

PSPACE=NPSPACE

NL=coNL

L=SL

DET=L^GapL (see Update 1)

Interactive Proofs

NP=PCP(O(log n), 3)

IP=PSPACE

AM = MAM = AMAM = ... [From Albert Atserias @atserias]

MIP=NEXP=PCP(poly,poly)

Alternating Turing machines

Σ_k P = ∃ Pi_k-1 P = NP^{Σ_k-1 P} = Σ_kTIME(poly(n)) [from Lance]

AP=PSPACE

APSPACE=EXP

Circuit classes within P

NC¹=5-PBP

ACC⁰=branching programs over solvable monoids

P=AuxPDA

SAC¹ = LogCFL [from Michael Levet @Michael_Levet]

REG = DSPACE(O(1)) = NSPACE(O(1)) [from Levet]

REG=DTIME_1tape(o(n log n))

AC^k = log^k time on a CRCW PRAM

Quantum

QIP=PSPACE

MIP*=CE

QMA_log (1)=BQP [from Martin Schwarz @martin_schwarz]

QMA_log (poly)=QCMA [ditto] 

QAC⁰_f = QNC⁰_f [from Ale `Scinawa' Luongo @scinawa]

QMA(k) = QMA(2) for any k ≥ 2 [from Sarvagya Upadhyay @sarvagya82]

Algebraic complexity

VP=VNC²

VDET=VABP=VP_s=VP_ws

VP_e=VABP₃

border-VP_e=border-VABP₂

For bilinear maps, tensor rank=Theta(algebraic circuit size)

Logical characterizations

FO=AC⁰

AC=NC=FO[poly(log)]

∃SO=NP

P = FO + LFP on ordered structures [thanks to Lance, and Michael Levet]

Kolmogorov-random strings as oracles

EXP=NP^R_Kt

PSPACE=ZPP^R_KS

P=COMP∩{dtt reducible to R_KU}

Almost-classes

AlmostP=BPP

AlmostNP=AM

AlmostPSPACE=BP^exp.PSPACE

---

Updates

1. March 17th update, h/t Eric Allender: Using Cook's original definition of DET as problems NC¹-reducible to the integer determinant, apparently this equality is not known! See Eric's recent guest column in SIGACT News for details and a $1000-prize related to this question, along with many other interesting open questions.