1
$\begingroup$

How can we prove that the language $COF=\{M\mid L(M)\text{ is cofinite}\}$ is m-complete for the class $ Σ_3^0$ ?
I have shown that $COF\inΣ_3^0$ but I can't prove that $COF$ is m-hard for $Σ_3^0$ which means that every other problem $L\in Σ_3^0$ satisfies $L\leq_m COF$.

$\endgroup$
1
$\begingroup$

Your problem is not so trivial, though classical. See the proof of Corollary 11.9 in lecture notes of Kevin T. Kelly.

$\endgroup$

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.