The tag has no usage guidance.

learn more… | top users | synonyms

2
votes
1answer
54 views

What is the difference between AM and IP

Intro I am trying to understand how those two models of interactive proof are different. I understand that $\text{AM}$ relies on public coins (the prover knows the random bits used by the verifier) ...
4
votes
0answers
31 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 ...
4
votes
1answer
67 views

Why there is no constraint on “Prover” in definition of $IP$?

According to the definition of $IP$ given in Sanjeev Arora and Barak there is no constraint on the running time of the "Prover" ( when "verifier" sends a message to the "Prover" and expects a message ...
1
vote
0answers
16 views

Reasoning approaches for implementing a Knowledge-based System?

What are the major approaches in implementing a Knowledge-based System (KBS)? Approaches used to take decisions in a KBS that I have come across so far are the case-based and rule-based reasoning ...
9
votes
0answers
73 views

Are there any known AM-complete problems/is AM-complete well defined?

I'm curious about whether there are any complete problems in the Arthur-Merlin complexity class. Graph Non-Isomorphism (GNI) seems to be the canonical example of a problem in AM, but it's probably not ...
1
vote
1answer
37 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
134 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
102 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 ...
6
votes
2answers
159 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
216 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 ...
4
votes
1answer
563 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
164 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 ...