[Solved]: proving $P \subseteq PCP(0,O(log(n))$

Problem Detail: 

I was working on proving this one and I've solve one direction as follows :
to prove that $P \subseteq PCP(0,logn)$ I said :
let $M$ be deterministic polynomial TM that accepts $L \in P$ ,we want to show that we can there exists a proof system which consists of prover and deterministic polynomial verifier that have access to an oracle and make at most $O(log(n))$ queries and $\forall x \in L$ $\exists \pi _x $suchthat the verifier always(i.e. probability =1) accepts and $\forall x \notin L$ always reject what ever the proof was.
the prover and the verifier will be the machine $M$ (since no randomness required) and $\pi _x$ will be: run M and obtain solution denoted by : $ANS$ send it to the verifier then the verifier checks if $ANS$ is the same and rejects or accepts accordingly ... this proves that: $P \subseteq PCP(0,O(1)) \subseteq PCP(0,O(log(n)) $

Asked By : Fayez Abdlrazaq Deab

Answered By : Luke Mathieson

As Kaveh points out, any problem in $P$ by definition can be solved in polynomial time by a Turing Machine, so it in effect produces its own proof and checks it, hence $P = PCP[0,0]$ and the inclusion you want to show is trivial.

What's more interesting is to show that $PCP[0,O(\log n)] \subseteq P$ (and hence equal).

Hint:

Try and think of why a proof that's only logarithmic in the size of the input isn't giving more information than you could work out. The sub question here, is why can we consider the proof to only be logarithmically sized?

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/11683

 Ask a Question

 Download Related Notes/Documents