if a language $L \in$ coNP, i.e. it's complement is in NP, then does L have a deterministic turing machine that decides it?

i think that this is false, but am unsure how to show it? my guess is using the fact that L is in NP, but i thought problems in NP do not necessarily need a deterministic turing machine to decide it, just a deterministic turing machine to verify it

  • $\begingroup$ Consider for example the TAUTOLOGY problem: given a boolean formula $F$, does $F$ have a true value for every assignment of values to $F$'s variables? This problem is complete for co-NP. There is an obvious algorithm to decide it: try every possible assignment of values and check each one to see if $F$ has a true value. $\endgroup$ – MJD May 19 '15 at 19:14

Actually because $NP$ and $coNP$ are subsets of $EXP$, there always is a deterministic touring machine deciding any of these. The problem is that it is a machine with a very long running time.

For an $NP$-language $L$, a deterministic $EXP$-TM deciding $L$ is simply the "try all verification candidates" (These are of polynomially bounded length, also called (nondeterministic) computation paths of the $NP$-TM) in order. If one of these paths was accepting, accept, else decline.
An analogous construction is possible for $L\in coNP$.


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.