Questions tagged [interactive-proof-systems]

The tag has no usage guidance.

15 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
201 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 ...
115 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 ...
35 views

Statement of the Goldwasser-Sipser Set Low Bound Protocol

I'm trying to understand the statement of the Goldwasser-Sipser Set Low Bound Protocol as presented in "Computational Complexity: A Modern Approach" by Arora and Barak. In particular, I'm ...
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), ...
15 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 ...
15 views

Would $\mathsf{P=BPP}$ imply $\mathsf{dIP=IP}$ and if not then why?

Complexity class $\mathsf{IP}$ includes all problems that can be solved using an interactive proof system where the verifier is a probabilistic polynomial time machine, and the prover is a machine of ...
39 views

Non-Interactive Zero Knowledge Proofs: zk-snarks and zk-stark

I read up on an abstract example of ZKPs (the cave and the door), but I'm trying to understand NIZKs (specifically zk-snarks and zk-stark). All the examples I can find online seem to have some ...
24 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 ...
14 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, ...
216 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 ...
79 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 ...
73 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 ...