# Tag Info

## Hot answers tagged interactive-proofs

18

If you want to restate the definition of MA in terms of PCP, you need another parameter for PCP, namely the proof length. MA is clearly the same as PCP with polynomial randomness, polynomial queries, and polynomial-length proofs. Usually the proof length in PCP is not restricted (that is, it is bounded only implicitly by randomness and queries), but this ...

16

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

13

Any answer to a question of the form, "What is the real reason that..." will necessarily be somewhat subjective. However, for the particular case of IP = PSPACE, I think that a pretty good case can be made that arithmetization is indeed the key, by observing that while IP = PSPACE does not relativize, it does algebrize in the sense of Aaronson and Wigderson....

12

Allowing completeness error has no problem, and it is often considered. Here are some pointers. On the other hand, generally speaking, disallowing soundness error removes the power of a model significantly. In the case of interactive proof systems, disallowing soundness error renders interaction useless except for one-way communication from a prover to a ...

12

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

11

This is not known, but as domotorp stated, it is believed not to be the case. First, note that $\mathsf{P} = \mathsf{BPP}$ doesn't say that randomness isn't useful in any context, just in the context of poly-time decision problems. For example, just assuming $\mathsf{P} = \mathsf{BPP}$ is already not known to imply that $\mathsf{AM} = \mathsf{NP}$ (and the ...

11

Tsuyoshi Ito answered the question literally, but I wanted to comment about the semantics of MA and PCP and how they differ. MA is the probabilistic version of NP, i.e., the verifier gets to also use poly-many random bits. In PCP we may refer to the "randomness" of the verifier, but usually the randomness is logarithmic in the running time of the verifier, ...

11

Under a hardness assumption, namely, that the complexity class $E = DTIME(2^{O(n)})$ requires circuits of exponential size, suffices to derandomize $MA$, so that $MA = NP$. In fact, the derandomization is to show that $BPP = P$ (see Impagliazzo-Wigderson or Sudan-Trevisan-Vadhan) . But since in $MA$ the verifier is a $BPP$ machine, we can replace it with a ...

9

In the definition of class IP(k), the interaction always ends with prover’s message. Otherwise there is no use for the last message (why?). The situation is different for the definitions of public-coin interactive proof systems (also known as Arthur-Merlin proof systems), where sending a message from the verifier to the prover is the only way for the ...

8

Does exponential decrease also happen in continuous case? No. Feige and Verbitsky [FV02] showed that for every n, there is a game G (with finite sets of questions and answers) such that v(G)≤3/4 and v(Gn)≥1/8. Because your formulation generalizes games with finite sets of questions and answers of any size, parallel repetition (of any finitely many times) ...

8

By request, I’ll turn the comment into an answer. Toda’s theorem says that $\mathrm{PH\subseteq BP\cdot\oplus P}$. Since $\mathrm{BP\cdot AM=AM}$, this shows the following implication: if $\oplus\mathrm P\subseteq\mathrm{AM}$, then the polynomial hierarchy collapses to $\mathrm{PH=AM=coAM}$. (In fact, the whole $\mathrm{Mod_2PH}$ hierarchy collapses to $\... 6 This question seems a little confused. The class of decision problems solvable efficiently on a quantum computer is BQP, while on a classical computer it is either P or BPP depending on exactly how you define things. An interactive proof is something entirely different. It is a protocol which allows a prover to prove, beyond reasonable doubt, the outcome of ... 6 This is a full answer to the problem which does not use Merlin at all. Deléglise-Dusart-Roblot [1] give an algorithm which determines the number of primes up to$x$that are congruent to$l$modulo$k,$in time$O(x^{2/3}/\log^2x).$A modification of the algorithm of Lagarias-Odlyzko [2] allows the same to be computed in time$O(x^{1/2+o(1)}).$Using ... 5 This is an answer to the last question: MA in the query complexity model. It isn't always possible to make the prover do all the work (or even any work at all). The reason is that an MA-prover is trying to convince you that the answer is YES. But the problem can be chosen so that in the YES case, there's nothing interesting that the prover can tell you. ... 5 An oracle separation is easy to show. I'm not sure which paper showed it first, but for example you can already show that there exists an oracle$X$such that$\mathsf{NP}^X \not\subset \mathsf{QSZK}^X,$which implies$\mathsf{AM}^X \not\subset \mathsf{SZK}^X$because$\mathsf{NP}$is in$\mathsf{AM}$and$\mathsf{SZK}$is in$\mathsf{QSZK}$. See ... 4 The basic idea here is that any operation that uses measurement can be replaced by an operation that instead CNOTs qubits onto ancillae. Any circuit with an intermediate measurement can be converted to a circuit that only has measurement as the last step. Doing so involves performing three simple transformations again and again: Moving measurements onto a ... 2 It will depend on the model of communication: (1) If the proof is known by both players, (2) if only parts of it is known by Alice and the rest by Bob, or (3) if only one of the players receives the proof (say Alice). Plus, if the communication uses public or private coins. For instance, in (3) with public coins, Merlin could send a copy of y to Alice, and ... 2 I think you are confusing zero knowledge with soundness. Fix some language$L$. [Adaptive] soundness for NIZK says, roughly, that when$\sigma$is chosen at random a prover cannot find a$y \not \in L$and a proof$\pi$for which a verifier will accept. Zero knowledge says that, for any$y \in L$, a simulator can output$(\sigma, \pi)$that is ... 2 No, but I don't know what would count as a proof. People conjecture P=BPP and IP$\ne$NP, if that is good enough. 2 According to this paper: https://arxiv.org/pdf/1509.09180.pdf The client only needs the ability to prepare random single-qubit pure states. You may also look at this paper for more information: https://link.springer.com/article/10.1007/s00224-018-9872-3 1 In his simplified proof of the parallel repetition theorem, Holenstein gives the following explicit bound on the value of the$n$-fold parallel repetition of a game with value$v$: $$\left(1-\frac{(1-v)^3}{6000}\right)^{n/\log(|\Sigma_1|\cdot |\Sigma_2|)},$$ where$\Sigma_1, \Sigma_2$are the alphabets of the two players. It's not clear to me that Raz's ... 1 The prover and the simulator must both be able to generate the proof, but given different inputs. The Prove functionality gets as input the CRS$\sigma$, the statement$y$and the witness$w$, and outputs$\pi$. The soundness requirement postulates that nobody should be able to create$\pi$for$y \not\in L$, given$\sigma$as an input. However, zero-... 1 The answers above addressed your concerns, but I wanted to add a complete description of the definition of the class IP and AM and MA here as well. Interactive Algorithms Terminology We have a prover$P$, a verifier$V$, and they are talking about some problem with language$L$. They are given a string$x$that both can see, then$P$is trying to ... 1 Koiran's paper Hilbert's Nullstellensatz is in the Polynomial Hierarchy provides a public-coin Arthur-Merlin protocol for establishing that a system of$m$equations on$n$unknowns has a solution in$\mathbb{C}^n$, contingent on the Generalized Riemann Hypothesis. Here Merlin finds a prime$p$with$H(p)=0$for some random hash$H$, along with a solution$(...

1

Determining that $20$ is the diameter (God's number) of the Rubik's Cube Group $G$ under the half-turn metric with Singmaster generating set $s=\langle U, U', U^2, D, D', D^2,\cdots\rangle$ was a wonderful result. I'm curious about follow-up questions, such as determining how many half-turn twists $m$ it would take to get the cube fully "mixed" to $\epsilon$...

Only top voted, non community-wiki answers of a minimum length are eligible