Comprobadores y resolvedores

Comprobación	Resolución
En un problema de decisión se verifica que una pareja hipotética $(\mbox{\bf x},\mbox{\bf y})\in N^m\times N^n$ es, en efecto, una pareja de la forma $(\mbox{\it Instancia},\mbox{\it Soluci\'on})$	En un problema de solución se construye una correspondiente Solución para cada Instancia dada.
No-determinismo	Determinismo
En un problema de decisión se parte de una pareja hipotética $(\mbox{\bf x},\mbox{\bf y})\in N^m\times N^n$ . Queda indeterminada la manera en la que se obtiene $\mbox{\bf y}$ dada $\mbox{\bf x}$ .	En un problema de solución se construye algorítmicamente la correspondiente Solución de una Instancia dada.

$\begin{displaymath}\mbox{\bf x}\in \mbox{\rm dom}(A)\;\Leftrightarrow\;\exists \mbox{\bf y}\in N^n:(\mbox{\bf x},\mbox{\bf y})\in A.\end{displaymath}$

Observación 2.1 Las siguientes proposiciones son inmediatas:

1.

Sea D_A un resolvedor del problema A. Podemos construir un comprobador N_A como sigue:

Dado $(\mbox{\bf x},\mbox{\bf y})\in N^m\times N^n$ , hacemos $\mbox{\bf y}_0=D_A(\mbox{\bf x})$ .
Si $\mbox{\bf y}=\mbox{\bf y}_0$ entonces se reconoce positivamente. Se rechaza en otro caso.

2.

Sea N_A un comprobador del problema A. Podemos construir un resolvedor D_A como sigue:

Enumeramos el espacio de posibles soluciones $N^n=\left(\mbox{\bf y}_i\right)_i.$
Para cada i verificamos con N_A si acaso $(\mbox{\bf x},\mbox{\bf y}_i)\in A$ , y suspendemos esta iteración la primera vez que se tiene una respuesta positiva.