QA task and promise domain

A decision task is a root promise pair $(Y,N)$ of disjoint subsets of $\{0,1{\}}^{\ast }$, as in Promise problem: its promise domain is $Y\cup N$, and the required output is yes on $Y$ and no on $N$. No correctness condition is imposed outside that promise.

A search task is a pair $(D,R)$ where $D\subseteq \{0,1{\}}^{\ast }$ is the promise domain and $R\subseteq \{0,1{\}}^{\ast }\times \{0,1{\}}^{\ast }$ is a witness relation. On each $z\in D$, a correct solver must output a binary string $w$ with $(z,w)\in R$. It has no output obligation for $z\mathrm{\notin }D$. Unlike a decision task, a search task need not divide its promise into yes and no sets.

For either task, an input encoding and input-length convention are specified separately; correctness is required only for encoded inputs in the declared promise.