*Guest post by Josh Grochow*

On the birdsite, Jay Cummings tweeted:

TOP 5 IDENTITIES OF ALL TIME

— Jay Cummings (@LongFormMath) February 8, 2023

5. You

4. Can't

3. Rank

2. Identities

1. e^{iπ}+ 1 = 0

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^{RKt}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 Σ
_{2}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:

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

quasi-poly
Frege =quasi-poly noncommutative formula IPS

**Space classes**

DET=L^{GapL} (see Update 1)

**Interactive Proofs**

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

**Alternating Turing machines**

Σ_{k} P = ∃ Pi_{k-1} P = NP^{Σk-1 P} =
Σ_{k}TIME(poly(n)) [from Lance]

**Circuit classes within P**

ACC^{0}=branching
programs over solvable monoids

SAC^{1} = 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**

QMA_{log} (1)=BQP [from Martin Schwarz @martin_schwarz]

QMA_{log}
(poly)=QCMA [ditto]

QAC^{0}_{f} =
QNC^{0}_{f} [from Ale `Scinawa' Luongo @scinawa]

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

**Algebraic complexity**

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

**Logical characterizations**

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

**Kolmogorov-random strings as oracles**

P=COMP∩{dtt reducible to R_{K}U}

**Almost-classes**

Updates

- March 17th update, h/t Eric Allender: Using Cook's original definition of DET as problems NC
^{1}-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.

Not exactly a complexity identity, but also "Turing equivalence" leads to some suprising "identities", too.

ReplyDeleteNice Thursday complexity post.

ReplyDeleteMany interesting ones in regular languages too: MSO=REG, FO=Star-Free, ...

ReplyDeleteTo explain upon the "AC0 = FO":

ReplyDeleteIf we extend FO with arithmetic predicates (i.e., addition and multiplication), denoted FO(+,x), then we get that FO(+,x) = DLOGTIME = DLOGTIME-uniform AC0.

If we have FO with the ability to use an arbitrary numerical predicate, denoted FO(Arb), then we get that FO(Arb) = non-uniform AC0.

Then, in line with the above anonymous comment, if we extend FO with an ordering relation, denoted FO(<) (i.e., FO over ordered structures), then we get that FO(<) = star-free regular languages.

Subtle distinctions but important because FO(<) \subset FO(+,x) \subset FO(Arb).

Correction: It should be "FO(+,x) = Logarithmic Time Hierarchy = DLOGTIME-uniform AC0".

DeleteDo you mean MIP*=RE?

ReplyDelete- Michael C.

RE (recursively enumerable) and CE (computably enumerable) are the same class. I find the latter more appealing.

Delete