# Questions tagged [interactive-proof-systems]

The tag has no usage guidance.

12 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
197 views

### “Essential” problem for MA

I am trying to understand different interactive proof systems, in particular AM and MA. Is there a typical problem for the complexity class MA as Graph-NonIsomorphism problem is for AM? Is there ...
110 views

### Interactive proofs for coNP languages proof clarification

I was reading a paper by Lance Fortnow and Michael Sipser. "Are there interactive protocols for co-NP languages?" Information Processing Letters 28 v5 (1988), pp. 249-251. An online version of the ...
61 views

### Proving a pattern exist in a string without revealing where

Some time ago i read the following problem (i don't remember the article from which i read it from) : "Suppose you are given a picture where the goal is to find waldo (from the game where is waldo), ...
14 views

### Why the soundness error in the $\mathrm{IP}$ of GNI can implicate $\mathrm{\Sigma_2} \subseteq \mathrm{\Pi_2}$ if GNI is co-NP-Complete?

PDF here shows a way to proof GI is NP-Complete $\implies \Sigma_2 = \Pi_2$. In the last step, it writes following: In other words, (1) is false in this case as required. Book Computational ...
19 views

### Proving (relativized) upper bounds against SZK

Does anyone know of any instances where we've been able to show that some complexity class is strictly harder than SZK relative to some oracle? In general, it seems that SZK is really hard (for ...
13 views

### Practical applications of multi-prover interactive proof protocols

A multi-prover interactive proof protocol, as described here, consists of computationally unbound provers $P_1,P_2,\ldots$ which together convince a polynomial-time verifier $V$ of some proposition, ...
124 views

### Perfect Completeness of AM protocols?

I understand the idea behind making a MA protocol perfectly complete. In a MA protocol, Merlin sends a proof $\pi$ which Arthur checks with his machine $V$ by plugging in some random bits $r$ such ...
78 views

### Interactive protocols for showing knots are “hard” to untie

Given two graphs $G_1$ and $G_2$, a zero-knowledge interactive protocol for a prover to convince a verifier that $G_1\not\cong G_2$ entails: The verifier choosing a random $i\in\{1,2\}$ The verifier ...
64 views

### Why does the proof that #SAT is in IP stop after m rounds?

I've been struggling to understand why the interactive proof for #SAT stops after only $m$ rounds, where $m$ is the number of variables in the formula $\phi$. I understand that two polynomials of ...
53 views

### Use of Mizar for algorithm specification and automatic analysis and discovery of algorithms?

Is it possible to use Mizar Mathematical Library for the specification of algorithms at the same detalization level as the implementation of the algorithm in industrial programming language? Mizar ...