1
$\begingroup$

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?

$\endgroup$

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
2
  • $\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
    Commented May 23, 2020 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
    Commented May 23, 2020 at 14:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.