# Languages in coNP

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

• 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. – 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$.