snippetMinor
How to show a set is $\Pi_2$ complete
Viewed 0 times
showpi_2completehowset
Problem
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?
Solution
To show that the language is $\Pi^0_2$ complete you have to show two things:
-
The language is $\Pi^0_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.
-
The language is $\Pi^0_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.
Context
StackExchange Computer Science Q#3098, answer score: 3
Revisions (0)
No revisions yet.