3
$\begingroup$

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...)

$\endgroup$

1 Answer 1

7
$\begingroup$

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.

$\endgroup$
1
  • 2
    $\begingroup$ thank you for clarification (all your points were helpful!). I see now that the question has an ill-posed title:), since $\Sigma^1_1$ is from the arithmetical hierarchy, not from the polynomial one. It also became clear that the picture I linked refers to the polynomial hierarchy. Also, "highly undecidable" is clear now: "$\Sigma^1_1$-hard is highly undecidable" means that it is much higher ("infinitely higher") in the (arithmetical) hierarchy than the closest decidable $\Delta^0_1$ (which is $\Sigma^0_1 \cap \Pi^0_1$). $\endgroup$
    – Ayrat
    Feb 1, 2018 at 16:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.