next up previous contents
Siguiente: Comprobadores y resolvedores Un nivel arriba: Clases de problemas Anterior: Problemas de decisión

Problemas de solución

Un problema de solución consta de un subconjunto $A\subset N^m\times N^n$ y consiste en localizar una solución, dada una instancia.


Instancia:
\begin{pagi}{34}Un punto $\mbox{\bf x}\in N^m$ .\end{pagi}
Solución:
\begin{pagi}{34}Una soluci\'on $\left\{\begin{array}{ll} \mbox{\bf y} &\mbox{\... ...f y}\in N^n:(\mbox{\bf x},\mbox{\bf y})\not\in A \end{array}\right.$\end{pagi}



En este caso el dominio de A es el conjunto $\mbox{\rm dom}(A)=\{\mbox{\bf x}\in N^m\vert\exists \mbox{\bf y}\in N^n:(\mbox{\bf x},\mbox{\bf y})\in A\}.$ Un autómata que resuelve el problema de solución es propiamente un calculador de soluciones de acuerdo con la ``regla'' A, o un resolvedor del problema en el sentido estricto.
Guillermo Morales-Luna
2000-07-10