3
$\begingroup$

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?

$\endgroup$
4
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you! Is there any information related to decidability that I can assume then for the Σ02 class of problems and Π02 class of problems? It seems like given Σ02 is the class of problems that can be decided by a TM that has an oracle for the halting problem, that it cannot be semi-decidable (computably enumerable) and must be fully undecidable. And then given Π02 is its complement, Π02 problems must be fully undecidable as well. Is this the right thought process? $\endgroup$ – Sarina Jan 4 '15 at 22:18
  • $\begingroup$ Also, if I wanted to prove that a problem is in the Σ02 class, should I show that there is a TM with an oracle for the halting problem that decides it? Thanks so much! $\endgroup$ – Sarina Jan 4 '15 at 22:19
  • $\begingroup$ 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. $\endgroup$ – David Richerby Jan 4 '15 at 22:31

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.