What does it mean for something to be $\prod_x^y$-complete or $\sum_x^y$-complete?
The search term you're looking for is &quot;arithmetical hierarchy&quot;.
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 &quot;level $0$&quot; 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.)