patternMinor
Is complexity class $\Sigma^1_1$ from polynomial hierarchy decidable?
Viewed 0 times
polynomialhierarchy1_1decidablesigmafromclasscomplexity
Problem
It is within polynomial hierarchy so I assumed it is decidable. The picture like this further hinted in that direction.
Yet, in a paper on page 2 I read
Satisfiability of [...] is highly undecidable (i.e., $\Sigma^1_1$-hard)
which implies that $\Sigma^1_1$-hard is undecidable. Do authors mean something else by "highly undecidable" or $\Sigma^1_1$-hard is really undecidable?
In the latter case, why is it included inside decidable PSPACE?
(or I misunderstanding things...)
Yet, in a paper on page 2 I read
Satisfiability of [...] is highly undecidable (i.e., $\Sigma^1_1$-hard)
which implies that $\Sigma^1_1$-hard is undecidable. Do authors mean something else by "highly undecidable" or $\Sigma^1_1$-hard is really undecidable?
In the latter case, why is it included inside decidable PSPACE?
(or I misunderstanding things...)
Solution
The confusion lies in using the same notation for the polynomial hierarchy and the arithmetical hierarchy.
The similarities are obvious, both notations talk about formulas with increasing quantifier complexity. The important distinction is that the polynomial hierarchy talks about bounded quantification, i.e. your space is limited (the witnesses must be of polynomial size). If the quantification is not bounded you have much more power, e.g. a formula for "program $p$ halts on input $x$" can be written in a $\Sigma_1$ form, which means that the halting problem is in the first level of the arithmetical hierarchy.
To avoid confusion the levels of the polynomial hierarchy are actually denoted by $\Sigma_i^p$, however when it is obvious from the context the $p$ is usually omitted. Note that the superscript in $\Sigma_1^1$ means that the quantification is over sets, which puts it above any level in the arithmetical hierarchy with quantification over the naturals.
The similarities are obvious, both notations talk about formulas with increasing quantifier complexity. The important distinction is that the polynomial hierarchy talks about bounded quantification, i.e. your space is limited (the witnesses must be of polynomial size). If the quantification is not bounded you have much more power, e.g. a formula for "program $p$ halts on input $x$" can be written in a $\Sigma_1$ form, which means that the halting problem is in the first level of the arithmetical hierarchy.
To avoid confusion the levels of the polynomial hierarchy are actually denoted by $\Sigma_i^p$, however when it is obvious from the context the $p$ is usually omitted. Note that the superscript in $\Sigma_1^1$ means that the quantification is over sets, which puts it above any level in the arithmetical hierarchy with quantification over the naturals.
Context
StackExchange Computer Science Q#87600, answer score: 7
Revisions (0)
No revisions yet.