Promise problem

A promise problem is a pair $(Y,N)$ of disjoint subsets of $\{0,1{\}}^{\ast }$. Its promise is $Y\cup N$. A deterministic solver must accept every word of $Y$ and reject every word of $N$, with either answer allowed elsewhere. The pair belongs to $\mathrm{P}\mathrm{r}\mathrm{o}\mathrm{m}\mathrm{i}\mathrm{s}\mathrm{e}\mathrm{P}$ if such a solver has a polynomial time bound on every input.

It belongs to $\mathrm{P}\mathrm{r}\mathrm{o}\mathrm{m}\mathrm{i}\mathrm{s}\mathrm{e}\mathrm{N}\mathrm{P}$ if there are a polynomial $p$ and a deterministic polynomial-time predicate $V(x,w)$ such that every $x\in Y$ has some $w$ with $\mathrm{\mid }w\mathrm{\mid }\le p(\mathrm{\mid }x\mathrm{\mid })$ and $V(x,w)=1$, whereas for every $x\in N$ every such $w$ has $V(x,w)=0$. The promise need not be decidable; either side or both sides may be empty. When $Y\cup N=\{0,1{\}}^{\ast }$, this is the ordinary language decision convention.