The interactive-proof-systems tag has no wiki summary.
2
votes
1answer
166 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
90 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 ...
7
votes
0answers
98 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 ...
