Problema de decisión

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».

Un problema de decisión también se puede formalizar como el problema de decidir si una cierta frase pertenece a un conjunto dado de frases, también llamado lenguaje formal. El conjunto contiene exactamente las frases para las cuales la respuesta a la pregunta es positiva. La pregunta anterior sobre los números primos se puede ver también como el lenguaje de todas las frases en el alfabeto {0, 1,..., 9} tales que el entero correspondiente es primo.

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 primo? Una instancia de este problema sería: ¿Es 17 primo?

Other Languages