5
votes
Accepted
How similar is the Goldwasser-Sipser Set Lower Bound Protocol to the Hashcash/Bitcoin Proof-of-Work?
I can see some similarity too, but only in a loose sense; there are also some significant differences.
Here's the similarity. Define $H_2(x)$ to be the first $d$ bits of $H(x||D)$. Then you can ...
D.W.♦
- 166k
4
votes
Accepted
Why is the complement of SAT in IP?
This is of course a consequence of $coNP \subset PH \subset PSPACE = IP$. But it can also be proven directly for UNSAT.
The basic idea is reducing the problem to zero-testing a sum over a polynomial ...
- 1,817
4
votes
Accepted
Interactive proof system for graph nonisomorphism
The slide describes a proof system for graph non-isomorphism. This is a way for the prover to convince the verifier that the two graphs are non-isormorphic. The soundness of this proof system derives ...
- 279k
4
votes
Is quadratic nonresiduosity in $\textbf{NP}$?
When the modulus is a prime $p$, you can compute quadratic residuosity in polynomial time using the Legendre symbol: $x$ is a quadratic residue mod $p$ iff $(x|p)=1$ or $0$.
When the modulus is a ...
D.W.♦
- 166k
3
votes
Statement of the Goldwasser-Sipser Set Low Bound Protocol
To succeed in distinguishing the case of $|S|\ge K$ from $|S|\le\frac{K}{2}$, you just need a constant gap (independent of $|S|$) in the acceptance probability in both cases. If you managed to achieve ...
- 13.6k
3
votes
Accepted
Easy proof of IP ⊆ PSPACE for private coins
Following the comments, below is a sketch of the proof that shows explicitly that there is no need for the coins to be public, as we can iterate over all random choices in polynomial space.
Sketch of ...
- 4,874
3
votes
Difference between $\Rightarrow$, $\Longrightarrow$ and $\rightarrow$ in Isabelle/HOL?
I haven't been able to find a good explanation of how these are different and relate to each other. I know that → is part of HOL and ⇒ and ⟹ part of Isabelle, but it seems that they are basically ...
- 163
3
votes
Accepted
Randomized Version of NP
The class you described is MA (interactive proofs consisting of one round where the prover, Merlin, sends one meassage to the verifier, Arthur, which then has to decide in probabilistic polynomial ...
- 13.6k
3
votes
Accepted
Are there deterministic and/or non-interactive zero-knowledge proofs?
Goldreich and Oren, in their paper Definitions and properties of zero-knowledge proof systems, show that if the verifier is deterministic then interactive proofs trivialize to RP, whereas if the ...
- 279k
3
votes
Prove count without revealing data
I think the usual way of doing this is that you hash each record (with a known cryptographically secure hash) and provide the client with $N$ hash values. The client chooses $k$ out of those hash ...
- 2,146
3
votes
Accepted
proving $IP^\star = NP$
If $x \in L$ then the probability that $(P,V)(x,r) = 1$ is positive, where $r$ is the randomness involved; the probability is over the choice of $r$. In particular, there is some $r$ such that $(P,V)(...
- 279k
2
votes
Does proofs are programs apply to any functional program?
In Haskell there are more programs than there are Coq proofs because Haskell has general recursion whereas Coq does not. (In fact Coq allows you to extract proofs into Haskell code.)
The reason that ...
- 31.2k
2
votes
Accepted
Symmetry of IP complexity class
There is no relativizing technique to show that $\mathrm{IP}$ is closed under complement.
Clearly, $\mathrm{NP}\subseteq\mathrm{IP}$.
Fortnow and Sipser gave an oracle relative to which $\mathrm{co}$...
- 2,303
2
votes
Accepted
Is there a Zero-Knowledge proof for SAT?
As usual with zero-knowledge proofs, this is an interactive proof. A prover is trying to prove that he has a satisfying assignment to some 3-SAT formula without giving away the assignment. A ...
- 8,149
2
votes
Is there a Zero-Knowledge proof for SAT?
Here is a zero-knowledge protocol for E3SAT, the variant of SAT in which each clause contains exactly three literals.
Consider an instance of E3SAT, consisting of variables $x_1,\ldots,x_n$ and ...
- 279k
2
votes
Accepted
Are there any NP-complete problems that are also in IP?
$$
IP = PSPACE
$$
According to wikipedia.
Thus $NP \subseteq IP$ and all NP-complete problems are in $IP$.
- 1,669
2
votes
Accepted
Difference between BPP, IP and AM complexity?
All of these classes can be described as consisting of languages accepted by certain Arthur–Merlin games. In these games, Merlin, an unlimited but potentially dishonest party, tries to convince Arthur,...
- 279k
2
votes
Accepted
is $IP=BPP^{NP}$
If $BPP = P$ (as is widely believed), then $BPP^{NP} = P^{NP}$. Since $IP = PSPACE$, $BPP^{NP} = IP$ would mean that $P^{NP} = PSPACE$, which seems unlikely (e.g. polynomial time hierarchy would ...
- 361
1
vote
Interactive proof for graphs with no non-trivial automorphisms
For a permutation $ \pi$ and a graph $G = (V,E)$ denote $\pi(G) = (V, \pi(E))$
under this notation, an automorphism $ \sigma $ will hold the following property:
$ \sigma(G)=G $
The protocol for a ...
1
vote
Accepted
Are there any known interactive proof protocols for NP-complete problems?
That article is talking about Arthur-Merlin protocols, which are a certain type of interactive protocol, with additional restrictions. IP = PSPACE doesn't apply, because not all interactive protocols ...
D.W.♦
- 166k
1
vote
Sumcheck protocol - how are these 2 polynomials different?
Your question is answered in the book itself, in the sentence you quote and the next few sentences thereafter. The Verifier doesn't get $s_1$. As the book says:
evaluating $s_1(r_1)$ is not an easy ...
D.W.♦
- 166k
1
vote
Accepted
Exponential sized graph 3-coloring is in MIP
This is meant to use a succinct encoding of the graph. That is, a graph on $2^n$ vertices $V=\{0,1\}^n$ with an edge set $E\subseteq\{0,1\}^n\times\{0,1\}^n$ is represented by a Boolean circuit $C$ in ...
- 2,231
1
vote
Accepted
How to start with verifying a formal proof programmatically?
In my opinion, it is quite difficult to answer your question because it is very broad. However, I'll try point out several facts that might help you choose a course of action. I will cite the proof ...
- 543
1
vote
Why does IP = PSPACE
I found it most easy to understand according to reference here for undergrad level:
It's easy to show that IP $\subseteq$ PSPACE . Suppose L ∈ IP . Then we have some verifier V
for L. The PSPACE ...
- 330
1
vote
Changing probabilities to 0/1 in definition of class IP
Suppose you have a (randomized) verifier $V$ such that, for all $Q,w$,
$$\begin{align*}
w\in L &\implies \Pr[V\leftrightarrow P\text{ accepts }w]\geq2/3\\
w\notin L &\implies \Pr[V\...
D.W.♦
- 166k
1
vote
How to remove a universal quantifier in Lean theorem prover
I've found an answer to the question I've posed. Here are the tactics I've used:
...
- 19
1
vote
Are there deterministic and/or non-interactive zero-knowledge proofs?
Here's a deterministic zero-knowledge proof of sorts, if there are any logic gaps please let me know!:
This zero knowledge proof involves proving you have a solution to three-colouring a map.
The ...
- 11
1
vote
Are there deterministic and/or non-interactive zero-knowledge proofs?
At the very core of Zero Knowledge proof systems, lies the fact that proofs are published by asking the party to prove the correctness of its knowledge, via any one of many methods to verify a ...
1
vote
Accepted
Are there any known AM-complete problems/is AM-complete well defined?
Since AM = BP.NP, it seems the go to "reduction" to AM relies on randomized reductions to 3SAT rather than the Karp reductions we use for deterministic complexity classes.
This is a wrong intuition. ...
- 2,303
Only top scored, non community-wiki answers of a minimum length are eligible