patternMinor
What does it mean for something to be $\prod_x^y$-complete or $\sum_x^y$-complete?
Viewed 0 times
sum_xwhatmeancompletefordoesprod_xsomething
Problem
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)$?
Solution
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$,
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.)
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.)
Context
StackExchange Computer Science Q#35547, answer score: 5
Revisions (0)
No revisions yet.