next up previous contents
Siguiente: Problemas de solución Un nivel arriba: Clases de problemas Anterior: Clases de problemas

Problemas de decisión

Un problema de decisión consta de un subconjunto $A\subset N^m\times N^n$ y consiste en decidir cuándo una instancia de él pertenece o no a A. Es pues de la forma:


Instancia:
\begin{pagi}{34}Un punto $(\mbox{\bf x},\mbox{\bf y})\in N^m\times N^n$ .\end{pagi}
Solución:
\begin{pagi}{34}Una respuesta $\left\{\begin{array}{ll} 1 &\mbox{\rm si } (\mb... ...ox{\rm si } (\mbox{\bf x},\mbox{\bf y})\not\in A \end{array}\right.$\end{pagi}



Un autómata que resuelve el problema de decisión es propiamente un reconocedor del conjunto A, o, en otras palabras, es un comprobador de parejas $(\mbox{\it Instancia},\mbox{\it Soluci\'on}).$
Guillermo Morales-Luna
2000-07-10