HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

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

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
problemwhatacceptancemeanhard0_2sigmafordoesand

Problem

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?

Solution

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.

Context

StackExchange Computer Science Q#35944, answer score: 4

Revisions (0)

No revisions yet.