5
$\begingroup$

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?

$\endgroup$
5
$\begingroup$

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.

$\endgroup$

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.