ASP-completeness
Here are some definitions about $\text{ASP}$ (none due to me).
Definition (Function problem). A function problem is a triple $\Pi = (D, S, \sigma)$, where $D$ is a set of problem instances, $S$ is a solution space, and $\sigma : D \to \mathbb{P}(S)$ assigns to each $x \in D$ the set $\sigma(x) \subseteq S$ of solutions to $x$. To solve an instance $x \in D$ is to either produce some $s \in \sigma(x)$ or report that $\sigma(x) = \emptyset$.
Definition ($\textbf{FNP}$). A function problem $\Pi = (D, S, \sigma)$ is in $\textbf{FNP}$ iff (1) there exists a polynomial $p$ such that $|s| \leq p(|x|)$ for every $x \in D$ and every $s \in \sigma(x)$ and (2) the language $\{ (x, s) \mid x \in D,\ s \in \sigma(x) \}$ is in $\textbf{P}$.
That is, (1) an $\textbf{FNP}$ problem has solutions of polynomial size and (2) given a candidate instance–solution pair $(x, s)$ of an $\textbf{FNP}$ problem, one can verify in polynomial time whether $s$ is a solution of $x$.
For example, a valid chess puzzle gives the starting player, White, one correct winning option each move until White gets a big advantage, checkmates, etc. If a position has multiple high-advantage moves for White, it’s a bad puzzle. This means puzzle composers have to check whether there is exactly one solution, i.e. an alternating quantified formula where each existential also requires uniqueness. For some games/problems outside of chess, this is tractable in polytime; we have some handy definitions for that.
Definition (Induced decision problem). Let $\Pi = (D, S, \sigma)$ be a function problem. The decision problem induced by $\Pi$ is $\Pi_D = (D, Y)$, where $Y = \{ x \in D \mid \sigma(x) \neq \emptyset \}$ is the set of instances admitting at least one solution.
Proposition ($\textbf{NP}$ and $\textbf{FNP}$ correspondence). For every decision problem $\hat{\Pi} \in \textbf{NP}$ there exists a function problem $\Pi \in \textbf{FNP}$ with $\Pi_D = \hat{\Pi}$, and conversely the decision problem induced by any $\Pi \in \textbf{FNP}$ is in $\textbf{NP}$.
The first direction is harder. If $\hat{\Pi} \in \textbf{NP}$ with verifier $V$, take $\sigma(x)$ to be the set of certificates accepted by $V$ on $x$. How do we get polynomialness?
The reverse direction is easier, because any $\textbf{FNP}$ certificate is a witness for membership in the induced language.
Definition ($n$-ASP). Let $\Pi = (D, S, \sigma)$ be a function problem and $n \in N$. The $n$-ASP of $\Pi$ is the function problem $\Pi_{[n]} = (D_{[n]}, S, \sigma_{[n]})$, where
\(\begin{aligned} D_{[n]} &= \{\, (x, S_x) \mid x \in D,\ S_x \subseteq \sigma(x),\ |S_x| = n \,\}, \\ \sigma_{[n]}(x, S_x) &= \sigma(x) \setminus S_x.\end{aligned}\)
I.e., an instance is a pair of an input $x$ and a set $S_x$ of $n$ known solutions to $x$; a solution is any solution to $x$ not already in $S_x$. There is a corresponding decision problem $(\Pi_{[n]})_D$ that asks whether such a further solution exists, and this decision problem could be called the $n$-ASDP of $\Pi$.
In the case of chess puzzles, say we start from an instance set $D$ containing one starting position. Solution spaces $S$ are strong strategies (gametree suffixes). Solution maps $\sigma$ associate starting positions with solution strategies. What problem does the composer want to solve? What value(s) does the parameter take?
Definition (ASP reduction). Let $\Pi_1 = (D_1, S_1, \sigma_1)$ and $\Pi_2 = (D_2, S_2, \sigma_2)$ be function problems. A polytime ASP reduction from $\Pi_1$ to $\Pi_2$ is a pair $\phi = (\phi_D, \phi_S)$ of polytime computable maps such that $\phi_D : D_1 \to D_2$, and for each $x \in D_1$, $\phi_S(x, \cdot)$ is a bijection from $\sigma_1(x)$ to $\sigma_2(\phi_D(x))$ (see Yato and Seta 2003). When there is such a reduction, then $\Pi_1 \leq_{asp} \Pi_2$.
I.e., an instance is a pair of an input $x$ and a set $S_x$ of $n$ known solutions to $x$; a solution is any solution to $x$ not already in $S_x$. There is a corresponding decision problem $(\Pi_{[n]})_D$ that asks whether such a further solution exists, and this decision problem could be called the $n$-ASDP of $\Pi$.
Now for the title card:
Definition (ASP-completeness). A function problem $\Pi$ is $\text{ASP}$-complete iff $\Pi \in \textbf{FNP}$ and $\Pi^\prime \leq_{asp} \Pi$ for every $\Pi^\prime \in \textbf{FNP}$.