# PCP deterministic emulation

Suppose that $S \in PCP(r(n),q(n))$, colclude that $S \in NTIME(2^r \cdot poly) \cap DTIME(2^{2^r q+r} \cdot poly)$

The idea of a nondeterminstic simulation of the $V$ on input $x$ is simple, guess a proof, check every string $y$ of the length $2^r$, and this simulation should take nondeterministic time $2^r \cdot poly$ because $V$ works in time $poly$ and there are $2^r$ string to check.

In case of deterministic simulation the same intuition is applied, the maximum length of the proof is $2^r \cdot q$ with non-adaptive queries, hence $2^{2^rq}$ number of proofs should be checked by deterministic emulation, therefore the total time is $2^{2^r \cdot q} \cdot poly$, not exactly what's required.

The problem is to show that $S \in NTIME(2^r \cdot poly) \cap DTIME(2^{2^r q+r} \cdot poly)$

## 1 Answer

Checking each of the possible proofs takes time $O(2^r\cdot poly)$, so checking $2^{2^rq}$ of them would take how much?

• $2^{2^r q} \cdot poly$ as I wrote, is it correct? – user16168 Jun 26 '13 at 3:22
• No. You want to do $2^{2^rq}$ times $O(2^r \cdot poly)$ work. How much do you get in total? – Yuval Filmus Jun 26 '13 at 5:06
• Oh, I see your point, there are at most $2^{2^r q}$ possible proofs, each one of them should be checked against $2^q$ possible outcomes of $q$ coins and each check take $O(poly)$, in total $O(2^{2^r q+r} poly)$ as required. Is it correct? In addition I need to justify the intersection $S \in NTIME(..) \cap DTIME(..)$, how to reason about it? – user16168 Jun 26 '13 at 5:17
• Now the calculation is right. To show that $S \in A \cap B$, you show that $S \in A$ and $S \in B$; that's the definition of intersection: $A \cap B = \{ S : S \in A \text{ and } S \in B \}$. – Yuval Filmus Jun 26 '13 at 5:18