# What does $\Sigma^0_2$-hard and $\Pi^0_2$-hard for a TM's Acceptance Problem mean?

I'm reading about a Turing Machine $M$ and it says the problem of deciding whether M accepts a string is "$\Sigma^0_2$-hard and $\Pi^0_2$-hard".

I haven't seen this kind of notation before and haven't found a good answer from searching. Is this a more specific form of saying NP-hard?

No, it's unrelated to NP-hardness. $\Sigma_n^0$ and $\Pi_n^0$ are the levels of the arithmetical hierarchy. $\Sigma_2^0$ is the class of problems that can be decide by Turing machines that have an oracle for the halting problem and $\Pi_2^0$ is the class of problems whose complement is in $\Sigma_2^0$.
There is the corresponding notion of the polynomial hierarchy, in which $\Sigma_1^\mathrm{P}$ is NP and $\Pi_1^\mathrm{P}$ is co-NP.
• All decidable and recursively enumerable problems are in $\Sigma_0^2$, too: you can decide them with an oracle machine that just happens to never use the oracle, for example. This is just like every problem in P being in NP, too, except that we know that $\Sigma^0_2\neq \Sigma^0_1=\mathrm{RE}$ so a $\Sigma^0_2$-complete problem is definitely not RE. And, yes, to show that something is in $\Sigma^0_2$, you just need to show you can decide it with a Turing machine that has an oracle for the halting problem. – David Richerby Jan 4 '15 at 22:31