0
$\begingroup$

Cook-Levin reduction is both deterministic polynomial time and parsimonious and that's mean that from every non deterministic Turing machine $M$ and string $w$ it is possible in polynomial time deterministically to create the boolean formula $\alpha_{M,w}$ so that every satisfying assignment of $\alpha_{M,w}$ is accepting path/route of $M$ with input $w$ and every falsifying assignment of $\alpha_{M,w}$ is rejecting path/route of $M$ with input $w$, and also $\alpha_{M,w}$ is in conjunctive normal form.

Therefore $\alpha_{M,w}$ is satisfiable if and only if $M$ with input $w$ has accept path/route and $\alpha_{M,w}$ is falsifiable if and only if $M$ with input $w$ has reject path/route.

I think that it is also possible from every non deterministic Turing machine $M$ and string $w$ it is also possible in polynomial time deterministically to create the boolean formula $\beta_{M,w}$ so that every satisfying assignment of $\beta_{M,w}$ is rejecting path/route of $M$ with input $w$ and every falsifying assignment of $\beta_{M,w}$ is accepting path/route of $M$ with input $w$ and $\beta_{M,w}$ will be also in conjunctive normal form.

Therefore $\beta_{M,w}$ is satisfiable if and only if $M$ with input $w$ has reject path/route and $\beta_{M,w}$ is falsifiable if and only if $M$ with input $w$ has accept path/route.

Am I right?

Improve this question
$\endgroup$
5
  • $\begingroup$ As far as I can tell, this is just what you'd get if you applied Cook-Levin to a machine that calculated the negation of $M$, e.g. you simulate $M$ and reject if it accepts and accept if it rejects. Basically, you can just swap the sense of "accept" and "reject". $\endgroup$ – Derek Elkins left SE Jan 14 '18 at 2:22
  • $\begingroup$ This sounds like finding the complement of non deterministic Turing machine, that is non deterministic Turing machine that decides the complement of the language that the original non deterministic Turing machine decides. Did you mean to swap the "accept" and "reject" paths and routes? $\endgroup$ – user82913 Jan 14 '18 at 3:00
  • $\begingroup$ I meant the special states that signal acceptance or rejection. I believe this does correspond to what you mean by swapping the "accept" and "reject" paths/routes. An accepting path/route is presumably an execution that terminates in the special "accept" state, and similarly for "reject". I do not mean changing what we mean by a non-deterministic TM accepting an input which is that there is some accepting path. If we do what I described in the previous comment, the new machine accepts an input if there is some rejecting path in the original machine. This is not the complement. $\endgroup$ – Derek Elkins left SE Jan 14 '18 at 3:16
  • $\begingroup$ I understood you. $\endgroup$ – user82913 Jan 14 '18 at 13:09
  • $\begingroup$ Sorry, but we're not here to check proofs that you've produced. Go carefully through what you've written and try to justify every single statement. $\endgroup$ – David Richerby Jan 18 '18 at 13:41