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)$


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

  • $\begingroup$ $2^{2^r q} \cdot poly$ as I wrote, is it correct? $\endgroup$ – user16168 Jun 26 '13 at 3:22
  • 1
    $\begingroup$ No. You want to do $2^{2^rq}$ times $O(2^r \cdot poly)$ work. How much do you get in total? $\endgroup$ – Yuval Filmus Jun 26 '13 at 5:06
  • $\begingroup$ 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? $\endgroup$ – user16168 Jun 26 '13 at 5:17
  • 1
    $\begingroup$ 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 \}$. $\endgroup$ – Yuval Filmus Jun 26 '13 at 5:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.