14
$\begingroup$

My first question is whether an interactive proof system characterisation is known for all the classic complexity classes. I would call P, NP, PSPACE, EXP, NEXP,EXPSPACE, recursive and recursively enumerable functions classic (among others). Specifically,is an interactive proof system characterisation known for recursive and recursively enumerable functions?

I only know that IP = PSPACE and that MIP = NEXPTIME. By `know' means I understand the definitions of objects on both sides of the equality and possibly understand the equality.

My second question is whether there is a graphical summary of different types of interactive proof systems and the complexity classes they characterise.

Specifically, I would like a reference to a figure similar to Immerman's picture of description complexity characterisations.

Improve this question
$\endgroup$
9
  • 3
    $\begingroup$ What do you already know? $\endgroup$
    – Tsuyoshi Ito
    Aug 19, 2012 at 12:33
  • 2
    $\begingroup$ There is more than 1 variable parameter in an interactive proof system: What's the power of the verifier, what's the power of the prover, what kind (and amount) of communication are they allowed, do they have pre-shared randomness, does the verifier have to read the entire message from the prover or does he have random access to the message, etc. $\endgroup$
    – Robin Kothari
    Aug 19, 2012 at 17:03
  • 2
    $\begingroup$ After a little more thinking, I do not think that I can answer your question adequately because interactive proof system is a broad topic in computational complexity theory. You may want to check Chapter 9 of Computational Complexity: A Conceptual Perspective by Goldreich or Chapters 8 and 11 of Computational Complexity: A Modern Approach by Arora and Barak. $\endgroup$
    – Tsuyoshi Ito
    Aug 19, 2012 at 22:16
  • 2
    $\begingroup$ @VijayD: Yes, that's part of the issue. In descriptive complexity characterizations, there's one variable (the logic), so as you go higher up from FO to SO, you go from AC0 to PH, etc. In interactive proof systems, there are so many variables that it's not clear that a nice landscape can be drawn. $\endgroup$
    – Robin Kothari
    Aug 19, 2012 at 22:21
  • 2
    $\begingroup$ I am not sure this question is well-specified enough. There is a trivial answer: every class can be "characterized" as an "interactive proof" where the prover basically does not do much and the verifier is powerful enough. The interesting thing about the IP=PSPACE and MIP=NEXP (and PCP[O(\log n), O(1)]=NP) results is that the verifier is surprisingly weak. $\endgroup$
    – Sasho Nikolov
    Aug 20, 2012 at 8:01

2 Answers 2

Reset to default
12
$\begingroup$

You can find many characterizations (particularly on space-bounded verifiers) in Condon's famous survey: The complexity of space bounded interactive proof systems.

Here is a list of some of them:

  • $ \mathsf{RE} = \mathsf{weak\mbox{-}IP(2pfa)} $, where 2pfa (the verifier) is a two-way probabilistic finite automaton.

  • $ \mathsf{R} = \mathsf{2IP(pfa)} $, where pfa (the verifier) is a one-way probabilistic finite automaton interacting with two provers.

  • $ \mathsf{NEXP} = \mathsf{2IP(pfa,poly\mbox{-}time)} $.

  • $ \mathsf{PSPACE} = \mathsf{IP(log\mbox{-}space,poly\mbox{-}time)} $.

  • $ \mathsf{NP} = \mathsf{oneway\mbox{-}IP(log\mbox{-}space,poly\mbox{-}time)} = \mathsf{oneway\mbox{-}IP(log\mbox{-}space,log\mbox{-}random\mbox{-}bits)} $.

  • $ \mathsf{P} = \mathsf{AM(log\mbox{-}space)} $, $ \mathsf{EXP} = \mathsf{AM(poly\mbox{-}space)} $, and etc.

Some recent (mostly quantum) results:

  • $ \mathsf{RE} = \mathsf{weak\mbox{-}AM(2qcfa)} $ by Yakaryilmaz, where 2qcfa (the verifier) is a two-way finite automaton having a constant-size quantum register.

  • $ \mathsf{R} = \mathsf{IP(2pca)} = \mathsf{AM(2qca)} $ by Yakaryilmaz, where 2pca (the former verifier) is a two-way probabilistic finite automaton with one counter and 2qca (the latter verifier) is a two-way quantum finite automaton with one counter.

  • Ito, Kobayashi, and Watrous gave a new characterization of $ \mathsf{EXP} $ based on quantum interactive proof systems with a double-exponentially small gap in acceptance probability between the completeness and soundness cases.

  • $ \mathsf{PSPACE} = \mathsf{QIP(poly\mbox{-}time)} $ by Jain, Ji, Upadhyay, and Watrous, where QIP is the quantum generalization of IP systems.

  • $ \mathsf{NP} $ is the class of languages for which membership has a logarithmic-size quantum proof with perfect completeness and soundness, which is polynomially close to 1 in a context where the verifier is provided a proof with two unentangled parts (Blier and Tapp).

  • $ \mathsf{NL} = \mathsf{weak\mbox{-}oneway\mbox{-}IP(2pfa,constant\mbox{-}random\mbox{-}bits)} $ by Say and Yakaryilmaz.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thanks! This is exactly what I wanted. I was at a loss of how to improve my question, which was too vague for experts, and am glad you understood my intent. $\endgroup$
    – Vijay D
    Aug 22, 2012 at 23:47
  • 2
    $\begingroup$ Well, then, why don't you mark it as the best answer? $\endgroup$
    – Cem Say
    Aug 23, 2012 at 13:09
  • 1
    $\begingroup$ Because who knows what tomorrow will bring? I would like to a week or 10 days after posting to decide. $\endgroup$
    – Vijay D
    Aug 24, 2012 at 8:17
16
$\begingroup$

NP is ofter characterized as a proof system in which the prover sends a polynomial-length proof to a deterministic polynomial-time verifier, and after which there is no interaction. The class of recursively enumerable languages can be characterized similarly by replacing "polynomial" with "finite".

Also, since the class of recursive languages R is the intersection of RE and coRE, you can characterize R as a proof system in which an all-mighty prover can convince a finite time verifier both in the validity of correct claims and in the invalidity of false claims.

The class EXP has a characterization in terms of a proof system with "competing provers" - i.e., a proof system in which there is a prover that tries to convince the verifier that the claim is true and a refuter that tries to convince the verifier that the claim is false. See the paper "Making games short" of Feige and Kilian for more details.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.