Tagged Questions

The tag has no wiki summary.

learn more… | top users | synonyms

1
vote
1answer
29 views

Why is there only a polynomial number of provers in multi-prover interactive protocols?

The paper On The Power of Multi-prover Interactive Protocols by Fortnow, Rompel, Sipser states the following: There are provers $P_1, P_2, \dots, P_k$ in a multi-prover interactive proof system such ...
0
votes
1answer
78 views

Implementation of datatypes in Haskell?

In Haskell, are datatypes converted to the "Church encoding" i.e. folding the data type. For example, given data N = Z | S N in Haskell, it can be converted to ...
4
votes
1answer
89 views

Number of rounds in interactive proofs - Arora & Barak

In the web draft of Arora and Barak, "Computational Complexity: A Modern Approach", the way I understand their definition of a round of interaction is that it consists of either the verifier or the ...
5
votes
1answer
102 views

Interactive Proofs for coNP

I am trying to understand interactive proof systems and tried the following problem as an exercise. We know that $PH \subseteq PSPACE$ and $IP=PSPACE$, so come up with (easy to understand) interactive ...
4
votes
1answer
206 views

Sketch an IP proof for minSAT

I have to sketch an IP proof for the minSAT problem. The minSAT problem is define in this way: For a given formulae find a satisfying assignment with a min subset of variables assigned to True; My ...
3
votes
1answer
201 views

Relation between interactive proof systems (IP), NP, coNP, PSPACE

I would like to ask you some clarification on the following question: know that ${\sf NP}$ is a subset of ${\sf IP}$ and also ${\sf coNP}$ it is a subset of ${\sf IP}$. So ${\sf IP}$ is a biggest ...
8
votes
0answers
116 views

“Essential” problem for MA

I am trying to understand different interactive proof systems. Is there a typical problem for the complexity class MA (like graph-nonisomorphism is for AM)? Is there a problem in MA but not known to ...