P is RE, but is the complement of the class of languages decidable in polynomial time also recursively enumerable?

If both are RE then this makes P recursive?


co-$\mathsf{P} = \mathsf{P}$. To see this, pick your favorite problem $A$ in co-$\mathsf{P}$, let $T$ be a Turing machine for the complement of $A$ (in $\mathsf{P}$) and construct a new Turing Machine $T'$ that simulates $T$, accepts if $T$ rejects, and rejects if $T$ accepts.

| cite | improve this answer | |
  • $\begingroup$ Thanks! what about the second question? As a consequence of your answer can I give a lexicographic order / index for the languages in P (or machines for languages in P)? This is something i could not do if P were only in RE and not in R. $\endgroup$ – DeeDee May 23 at 14:38
  • $\begingroup$ If both $C$ and and co-$C$ are in RE, then they are also both recursive. In your particular case $P$ is recursive. $\endgroup$ – Steven May 23 at 14:39

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.