World's most popular travel blog for travel bloggers.

PCP deterministic emulation

, , No Comments
Problem Detail: 

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

Asked By : user16168

Answered By : Yuval Filmus

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

Best Answer from StackOverflow

Question Source :

3200 people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback