Diferencia entre revisiones de «Problema de decisión»
Contenido eliminado Contenido añadido
pido referencias (la introducida es más bien una fuente primaria) |
|||
Línea 1:
{{referencias|matemáticas|t=20180302}}
{{otros usos|Duda}}
En [[teoría de la computación]], un '''problema''' es un conjunto de frases de longitud finita que tienen asociadas frases resultantes también de longitud finita. Un '''problema de decisión''' es un problema en donde las respuestas posibles son «sí» o «no».
Línea 6 ⟶ 7:
==Concepto intuitivo==
Se usa el término «problema» para designar a toda una clase de preguntas que tienen una estructura similar y cuya respuesta depende de ciertos parámetros de entrada. Una '''instancia''' es un caso particular que se obtiene de un problema al asignar valores concretos a los parámetros de entrada. Por tanto una instancia tiene una respuesta específica: «sí» o «no».
Un ejemplo típico de problema de decisión es la pregunta: ¿Es un número [[entero]] dado [[número primo|primo]]? Una instancia de este problema sería: ¿[[Diecisiete|Es 17 primo]]?
| |||