How can I prove that a set is complete for $\Pi_2$ complete? Can you give me an example proof? Say for $All_{TM}$ = Turing machines whose accepted language is all strings?


To show that the language is $\Pi^0_2$ complete you have to show two things:

  1. The language is $\Pi^0_2$

  2. Every $\Pi^0_2$ language is many-one reducible to your language

To show that your language is $\Pi^0_2$, informally, you need to know two things: (1) quantifiers over strings count the same as quantifiers over numbers, and (2) the predicate $P(M,\sigma)$ = "machine $M$ accepts string $\sigma$" is $\Sigma^0_1$. Your language is a universal quantifier in front of that $\Sigma^0_1$ relation, so it is $\Pi^0_2$.

To show that an arbitrary $\Pi^0_2$ language is many-one reducible to yours, it's easiest to show that some other language that you know is $\Pi^0_2$ complete is many-one reducible to your language. The details of that will depend on what languages you already know to be $\Pi^0_2$ complete. If you don't know any, then it helps to know that every $\Pi^0_2$ language is definable by a formula of the form $(\forall \sigma)(\exists \tau) R(\sigma,\tau)$ where $R$ is computable.


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.