Imagine a Problem $A$ with input size $n$ for which you can get a proof certificate (polynomial number of bits).

Next you try to use this string to verify if your problem is solved or not.

You know that verification gets almost as good as if you'd try to verify an $NP$-problem in the sense that the verification process itself is trying to solve a $co-$$RP$-Problem, meaning that everytime you get a proof string for $A$ the (polynomial time-) verifier will output "YES" with probability $1$ when it is correct and "NO" with probability $1/2$ when it is not a correct proof.

However, the verifier needs a polynomial amount of random bits $r(n)\in O(n^k)$ for this to make sure that the probabilities are as written above for one attempt of verification. Maybe think of all possible random bit strings as the search space which would be all "YES" if you had a correct proof and had to verify for every single possible random string (otherwise at least half of them were "NO").

For this question, to understand what type of complexity class I am actually trying to learn about here, I read about the $PCP$ theorem and how you can characterize $NP=PCP[O(log(n)),O(1)]$. On Wikipedia they also mentioned a weaker result $NP=PCP[n^3, 1]$ and that $PCP[poly(n),poly(n)]=NEXP$ which confuses me, probably because there is a mistake in my understanding of $PCP$. Here I was wondering if it is true that $NP=PCP[n^3,O(n^k)]$ (?) and would then $A\in NP$ for $n^3$ random bits?

Most importantly though, what complexity class does $A$ belong to and how do $(co-)RP$, $(co-)NP$, $NEXP$ and $PCP$ relate to $A$? Is $A$ well known?

Edit: To make this more precise in terms of the $PCP$ characterization: If $A$ only needs random bit strings of size $n^3$ then I think that $A\in PCP[n^3,O(n^k)]$, but we do not only use a portion of the proof of size $O(n^k)$, but the whole proof is at maximum of size $O(n^k)$. I don't know if that makes a difference since when reading about $PCP$ I read that you don't query every bit that there is, but a fraction of the available bits. Also $A$ uses non-adaptive queries.


1 Answer 1


Alright, I think I finally found what I was searching for. What I was trying to describe turns out to be the complexity class $MA$ because the proof is of polynomial size and we use the full proof and a polynomial amount of bits. It's similar to $NP$ but since we don't know whether $MA=NP$, only that $NP\subseteq MA$, we cannot say if $A\in NP$.

If anyone disagrees and wants to correct my answer or answer the question, I would be glad.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.