Thursday, March 16, 2023

Identities in Computational Complexity

Guest post by Josh Grochow

On the birdsite, Jay Cummings tweeted:


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 PA=NPA"), 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=NPRKt or AlmostP=BPP (AlmostP is the class of languages L such that {A : L is in PA} 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 Σ2P, 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=LGapL (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 = ∃ Pik-1 P = NPΣk-1 P = ΣkTIME(poly(n)) [from Lance]

AP=PSPACE

APSPACE=EXP

Circuit classes within P

NC1=5-PBP

ACC0=branching programs over solvable monoids

P=AuxPDA

SAC1 = LogCFL [from Michael Levet @Michael_Levet]

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

REG=DTIME1tape(o(n log n))

ACk = logk time on a CRCW PRAM

Quantum

QIP=PSPACE

MIP*=CE

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

QMAlog (poly)=QCMA [ditto] 

QAC0f = QNC0f [from Ale `Scinawa' Luongo @scinawa]

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

Algebraic complexity

VP=VNC2

VDET=VABP=VPs=VPws

VPe=VABP3

border-VPe=border-VABP2

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

Logical characterizations

FO=AC0

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=NPRKt

PSPACE=ZPPRKS

P=COMP∩{dtt reducible to RKU}

Almost-classes

AlmostP=BPP

AlmostNP=AM

AlmostPSPACE=BPexp.PSPACE


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

7 comments:

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

    ReplyDelete
  2. Nice Thursday complexity post.

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

    ReplyDelete
  4. To explain upon the "AC0 = FO":

    If 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).

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

      Delete
  5. Do you mean MIP*=RE?

    - Michael C.

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

      Delete