[Solved]: Proving that a language is not in P using diagonalization

Problem Detail: 

Pardon me if i'm missing something which is very obvious here but i cant seem to figure it out.

$E=\{ \langle M, w \rangle \mid \text{ Turing Machine encoded by $M$ accepts input $w$ after at most $ 2^{|w|}$ steps}\}$

We have to prove $E\notin P$

The book (Papadimitrou, Elements of the ToC) assumes $E\in P$ and it constructs another language (a diagonal one)

$E_1=\{\langle M\rangle \mid \text{ Turing Machine encoded by $M$ accepts input $M$ after at most $ 2^{|M|}$ steps}\}$

and takes its complement language $E_1'$ and it follows that with the assumption $E\in P$ , it is true that $E_1' \in P$

The question it then asks is the following: Say the polynomially bounded turing machine to decide $E_1'$ is $M^*$ then what happens when $M^*$ is presented with $M^*$ as an input? Now I understand it cant give an yes because that results in a contradiction. My doubt is where is the contradiction if the answer is no?

Asked By : swarnim_narayan

Answered By : Yuval Filmus

The idea (which doesn't quite work) is that given that $E'_1 \in P$, $M^*$ runs in time at most $2^n$ on an input of length $n$ (that's not quite true). Given that, if $M^*$ rejects $M^*$ then by the definition of $E'_1$, $M^*$ accepts input $M^*$ after at most $2^{|M^*|}$ steps, which is a contradiction.

The other direction, which you were happy with, is problematic: if $M^*$ accepts $M^*$ then by the definition of $E'_1$, $M^*$ does not accept input $M^*$ after at most $2^{|M^*|}$ steps. That's not a contradiction since our assumption that the running time of $M^*$ is $2^n$ was wrong - perhaps it's $2^{|M^*|} n$. So you need to be more subtle - presumably Papadimitriou addresses this.

Best Answer from StackOverflow

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

3.2K people like this

 Download Related Notes/Documents