7
$\begingroup$

I am trying to show that a decision problem is in $\Pi_1^1$. Because of this, I am looking for:

  1. Papers or books that present a complete and well-explained proof where a problem is shown to be in $\Pi_1^1$.
  2. Well-known problems that are in $\Pi_1^1$.

Any suggestions?

$\endgroup$

2 Answers 2

6
$\begingroup$

I think that a good well-studied problem may be the "recurrent tiling problem". For more references (with many use cases) consult the paper "Recurring Dominoes: Making the Highly Undecidable Highly Understandable" by David Harel [Sec. 2.1, 1].

[1] https://www.wisdom.weizmann.ac.il/~dharel/SCANNED.PAPERS/RucurringDominoes.pdf

$\endgroup$
2
  • 1
    $\begingroup$ A quite readable paper on tilings is also “The convenience of tilings” by Peter van Emde Boas $\endgroup$ Commented Oct 20, 2023 at 20:16
  • 1
    $\begingroup$ Thanks guys for the comments! At the end we were able to use some of the problems presented by Harel to reduce to and from : ) $\endgroup$ Commented Feb 8 at 11:08
6
$\begingroup$

The standard example of a $\Pi^1_1$ complete decision problem is the following:

Is $e$ an index for a Turing machine which (halts on all inputs and) computes a well-ordering of $\mathbb{N}$?

Let's write "$\mathcal{W}$" for the set of such $e$s.

Here, a well-ordering of $\mathbb{N}$ is a binary relation on $\mathbb{N}$ which is a linear order with the additional property that every (nonempty) subset has a least element. One inessential (but technically useful) variant of this is Kleene's $\mathcal{O}$, which basically focuses on "nicely presented" relations. Re: my parenthetical, detecting whether a Turing machine halts on all inputs is merely $\Pi^0_2$, so galactically weaker than what we're interested in.

It's a standard result (and a fun exercise to show) that $\mathcal{W}$ is $\Pi^1_1$ complete; that is, a decision problem is $\Pi^1_1$ iff it can be (computably many-one) reduced to $\mathcal{W}$. So $\mathcal{W}$ serves as a template for testing $\Pi^1_1$-ness analogously to the role that the halting problem serves for $\Sigma^0_1$-ness or (replacing "computably" with "polynomial-time-computably") that $\mathsf{SAT}$ serves for $\mathsf{NP}$-ness.

The basic idea behind proving that $\mathcal{W}$ (or $\mathcal{O}$) is $\Pi^1_1$ hard (this is the nontrivial part of $\Pi^1_1$ completeness in these cases) is as follows: given an arbitrary $\Sigma^1_1$ definition $\varphi$ and a number $n$, we build a tree $T_{n,\varphi}$ whose nodes represent "apparent counterexamples" to $\varphi(n)$ holding. An infinite path through $T_{n,\varphi}$ corresponds to a genuine counterexample to $\varphi(n)$, so we've reduced checking whether $\varphi(n)$ holds to checking whether $T_{n,\varphi}$ is well-founded. This isn't quite the same as "well-ordered," but now we use the Kleene-Brouwer construction to reduce well-foundedness to well-orderedness.

A nice general treatment of $\Pi^1_1$ complete sets and their properties - but focusing on the more technical $\mathcal{O}$ rather than $\mathcal{W}$ - can be found in the first section of Sacks' book Higher recursion theory.


EDIT: This next bit is really more set theory than complexity theory, but I think it's still worth mentioning:

One key bit of intuition (due to Kreisel if I have my history right) is that despite appearances $\Pi_1^1$ is the analogue of computably enumerable (c.e.) rather than co-c.e. Even more confusingly, $\Delta^1_1$ is the analogue of finite rather than computable. (For an example of the latter point, the $\Pi^1_1$ image of a $\Delta^1_1$ set is $\Delta^1_1$ again.)

This is explained via $\omega_1^{CK}$-recursion theory - the special case of $\alpha$-recursion theory with $\alpha=\omega_1^{CK}$ - as follows (with "$L_\alpha$" denoting the $\alpha$th level of Godel's constructible universe):

  • Classically, shifting from the natural numbers to the hereditarily finite sets we have "finite" = "element of $L_\omega$," and "c.e." = "$\Sigma_1(L_\omega)$."

  • The generalization to $\omega_1^{CK}$ is then "$\omega_1^{CK}$-finite" = "element of $L_{\omega_1^{CK}}$" and "$\omega_1^{CK}$-c.e." = "$\Sigma_1(L_{\omega_1^{CK}})$."

Note that $\omega$ (or $\mathbb{N}$ if you prefer) is $\omega_1^{CK}$-finite. It's not hard to show that $X\subseteq\omega$ is $\Pi^1_1$ in the usual sense iff it is $\Sigma_1(L_{\omega_1^{CK}})$. Conversely, though, we lose a crucial bit of combinatorics in passing to $\omega_1^{CK}$: a c.e. subset of a finite set is not finite but merely "subfinite." However, a computable subset of a finite set is finite. This corresponds to the fact that the theory $\mathsf{KP}$ (= basically the amount of set theory that $L_{\omega_1^{CK}}$ satisfies) entails $\Delta_1$ comprehension but not $\Sigma_1$ comprehension.

Why on earth am I saying all this? Well, in my opinion a lot of the properties of $\Pi^1_1$ sets become much simpler when thought of in terms of $\omega_1^{CK}$-recursion theory. If set theory puts you off, you may find "metarecursion theory" - basically $\omega_1^{CK}$-recursion theory but over (paths through) Kleene's $\mathcal{O}$ instead of $L_{\omega_1^{CK}}$ as such - to be a useful rephrasing; again assuming my history is right, this was how things were originally phrased by Kreisel and Sacks before the simplifying power of the shift to $\alpha$-recursion theory was fully understood.

$\endgroup$
2
  • $\begingroup$ Out of curiosity, why the downvote? $\endgroup$ Commented Oct 30, 2023 at 19:11
  • $\begingroup$ Thank you for your detailed reply! : ) $\endgroup$ Commented Feb 8 at 11:09

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.