Diferencia entre revisiones de «Problema computacional»

 

== Tipos de problemas abstractos ==

{{AP|Problema de decisión}}

En un '''problema de decisión''' cada instancia tiene asociada exactamente una solución "''sí''" o "''no''". Los problemas de decisión quedan completamente determinados por el conjunto <math>Y</math> de instancias que tienen asociada la solución "''sí''". Por ejemplo, el problema de decidir si una gráfica tiene o no un [[Camino hamiltoniano|ciclo Hamiltoniano]] queda completamente determinado su conjunto de soluciones "''sí''":{{Ecuación|<math>\mathrm{HAM}=\left\{G\mid G\text{ es una gráfica hamiltoniana}\right\}</math>}}Con esta representación el problema equivale a preguntar si una instancia <math>i</math> pertenece o no al conjunto <math>\mathrm{HAM}</math>. En general, los problemas de decisión siempre equivalen a decidir la proposición <math>i\in Y</math> donde <math>Y</math> es el conjunto de instancias con solución "''sí''". Una solución algorítmica para un problema de decisión es un algoritmo que calcula la función característica de <math>Y</math> o equivalente: {{Ecuación|<math>\chi_Y(i)=\begin{cases}1&\text{si }i\in Y\\0&\text{si }i\notin Y\end{cases}</math>}}