4
$\begingroup$

I'm having trouble understanding the definitions for complexity classes in the arithmetic heirarchy, and because of the naming schemes, "Googling" things is somewhat difficult. Can anyone provide me concrete examples of what it means for something to be $\prod_x^y$-complete or $\sum_x^y$-complete, and when we can say that a problem is undecidable for some $(x,y)$?

$\endgroup$
5
$\begingroup$

The search term you're looking for is "arithmetical hierarchy".

The arithmetical hierarchy

All of the following relates to the logical language of Peano arithmetic. The operations available to us are the unary successor function $S$, the constant $0$ and the binary relation $=$, all with the usual, obvious meanings. Variables range over the natural numbers.

In the notation $\Sigma_n^m$ or $\Pi_n^m$,

  • $\Sigma$ denotes a formula equivalent to one in prenex normal form with an existential quantifier outermost;
  • $\Pi$ denotes a formula equivalent to one in prenex normal form with a universal quantifier outermost;
  • $n$ denotes the number of quantifier blocks;
  • $m$ denotes the kinds of objects being quantified.

A formula is in $\Sigma_0^0=\Pi_0^0$ if it contains no quantifiers. A formula is in $\Sigma^0_{n+1}$ if it is equivalent to one of the form $\exists x_1, \dots, \exists x_k\,\varphi$, where $\varphi\in\Pi_n^0$. A formula is in $\Pi^0_{n+1}$ if it is equivalent to one of the form $\forall x_1, \dots, \forall x_k\,\varphi$, where $\varphi\in\Sigma_n^0$.

All of the quantifier aboves are first-order: they range over the natural numbers. Call the natural numbers "level $0$" objects and define level-$(m+1)$ objects to be sets of level-$m$ objects (or, equivalently, functions from level-$m$ objects to $\mathbb{N}$). $\Sigma_n^m$ and $\Pi_n^m$ extend the definition of $\Sigma_n^0$ and $\Pi_n^m$, respectively, by allowing quantification over objects at any level between $0$ and $m$, inclusive.

Completeness

So far, we've only talked about formulae but a set $X\subseteq \mathbb{N}$ is said to be in $\Sigma_n^m$ if there is a formula $\phi(x)\in \Sigma_n^m$ with one free-variable such that $X = \{x\mid \phi(x)\text{ is true}\}$; similarly for $\Pi_n^m$.

Completeness just means what it always means. A set is complete for $\Sigma_n^m$ if it's in $\Sigma_n^m$ and every other set in $\Sigma_n^m$ can be reduced to it (similarly for $\Pi_n^m$-completeness). The notion of reducibility is usually either many-one reductions or Turing reductions. So, for example, a set $Y$ is complete for $\Sigma_n^m$ under Turing reductions if, for every set $X\in\Sigma_n^m$, there is a Turing machine with an oracle for $Y$ that decides membership of $X$. For many-one reductions, we insist that the oracle is called only once and the result of the oracle must be the result of the Turing machine's computation. (Many-one reductions are the ones usually used to prove NP-completeness but, here, we're not restricting to polynomial-time reductions.)

$\endgroup$
  • $\begingroup$ Thanks for such a thorough answer! What does it mean, however, if we say something is $\Sigma_0^0$-complete, equiv. $\Pi_0^0$-complete? I'm having trouble understanding what sort of statements would lead to these completeness results? $\endgroup$ – Oliver Dec 20 '14 at 14:56
  • $\begingroup$ A set in $\Sigma_0^0$ is defined by a quantifier-free formula. So, for example, $\{x\mid x=S(S(S(0)))\vee x=S(0)\}$. As I recall, $\Sigma_0^0$ is exactly the set of finite subsets of $\mathbb{N}$ and their complements. Since all of those can be defined by Turing machines (actually, they're all regular), every set in $\Sigma_0^0$, except for $\emptyset$ and $\mathbb{N}$ is complete. $\endgroup$ – David Richerby Dec 20 '14 at 15:01
  • $\begingroup$ Shouldn't we be able to say then that a $\Sigma_0^0$-complete language is undecidable? $\endgroup$ – Oliver Dec 20 '14 at 15:03
  • $\begingroup$ If I'm correct that every $\Sigma_0^0$ language is finite or co-finite, then, as I said, they're all regular so they're "very" decidable! $\endgroup$ – David Richerby Dec 20 '14 at 15:16
  • $\begingroup$ Would the addition of a single $\forall$ quantifier block, a $\prod_1^0$-complete language, be undecidable? It would be extremely helpful to me to understand "where" undecidability begins in the arithmetical hierarchy. $\endgroup$ – Oliver Dec 20 '14 at 15:25

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.