Question

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?

Was it helpful?

Solution

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.

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top