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 véase 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?
Problema decidible
Si existe un algoritmo que pueda decidir para cada posible frase de entrada si esa frase pertenece al lenguaje, entonces se dice que el problema es decidible, de otra forma se dice que es un problema indecidible. Cuando existe un algoritmo que puede responder positivamente cuando la frase está en el lenguaje, pero que corre indefinidamente cuando la frase no pertenece al lenguaje se dice que el problema es parcialmente decidible. En teoría de la computabilidad, se estudia qué lenguajes son decidibles con diferentes tipos de máquinas. En teoría de la complejidad computacional se estudia cuántos recursos necesita un algoritmo decidible para ejecutar (recursos de tiempo, espacio, número de procesadores, tipo de máquina, etc.).
Ejemplos
Esos son algunos ejemplos de problemas de decisión expresados como lenguajes:
Las frases sobre el alfabeto {a, b} que contienen alternadas las letras a y b.
Las frases sobre el alfabeto {a, b, c} que contienen igual número de letras a y b.
Las frases que describen un grafo con aristas etiquetadas con números naturales que indican su longitud, dos vértices del grafo y un camino en el grafo que es el camino más corto entre esos dos vértices.
Las frases que describen una máquina de Turing y una cinta de entrada para esta máquina tal que la máquina se detiene en un tiempo finito al procesar esa entrada.
Los problemas de decisión son interesantes dado que todos los problemas formales (que incluye tanto lógicos como matemáticos) pueden ser redactados para que tomen la forma de un problema de decisión. Las soluciones al problema de decisión y al problema original se diferencian a lo sumo por un factor lineal.
problema, decisión, este, artículo, sección, necesita, referencias, aparezcan, publicación, acreditada, este, aviso, puesto, marzo, 2018, para, otros, usos, este, término, véase, duda, teoría, computación, problema, conjunto, frases, longitud, finita, tienen, . Este articulo o seccion necesita referencias que aparezcan en una publicacion acreditada Este aviso fue puesto el 2 de marzo de 2018 Para otros usos de este termino vease Duda En teoria de la computacion un problema es un conjunto de frases de longitud finita que tienen asociadas frases resultantes tambien de longitud finita Un problema de decision es un problema en donde las respuestas posibles son si o no Un problema de decision tambien se puede formalizar como el problema de decidir si una cierta frase pertenece a un conjunto dado de frases tambien llamado lenguaje formal El conjunto contiene exactamente las frases para las cuales la respuesta a la pregunta es positiva La pregunta anterior sobre los numeros primos se puede vease tambien como el lenguaje de todas las frases en el alfabeto 0 1 9 tales que el entero correspondiente es primo Indice 1 Concepto intuitivo 2 Problema decidible 3 Ejemplos 4 Vease tambien 5 ReferenciasConcepto intuitivo EditarSe usa el termino problema para designar a toda una clase de preguntas que tienen una estructura similar y cuya respuesta depende de ciertos parametros de entrada Una instancia es un caso particular que se obtiene de un problema al asignar valores concretos a los parametros de entrada Por tanto una instancia tiene una respuesta especifica si o no Un ejemplo tipico de problema de decision es la pregunta Es un numero entero dado primo Una instancia de este problema seria Es 17 primo Problema decidible EditarSi existe un algoritmo que pueda decidir para cada posible frase de entrada si esa frase pertenece al lenguaje entonces se dice que el problema es decidible de otra forma se dice que es un problema indecidible Cuando existe un algoritmo que puede responder positivamente cuando la frase esta en el lenguaje pero que corre indefinidamente cuando la frase no pertenece al lenguaje se dice que el problema es parcialmente decidible En teoria de la computabilidad se estudia que lenguajes son decidibles con diferentes tipos de maquinas En teoria de la complejidad computacional se estudia cuantos recursos necesita un algoritmo decidible para ejecutar recursos de tiempo espacio numero de procesadores tipo de maquina etc Ejemplos EditarEsos son algunos ejemplos de problemas de decision expresados como lenguajes Las frases sobre el alfabeto a b que contienen alternadas las letras a y b Las frases sobre el alfabeto a b c que contienen igual numero de letras a y b Las frases que describen un grafo con aristas etiquetadas con numeros naturales que indican su longitud dos vertices del grafo y un camino en el grafo que es el camino mas corto entre esos dos vertices Las frases que describen una maquina de Turing y una cinta de entrada para esta maquina tal que la maquina se detiene en un tiempo finito al procesar esa entrada Los problemas de decision son interesantes dado que todos los problemas formales que incluye tanto logicos como matematicos pueden ser redactados para que tomen la forma de un problema de decision Las soluciones al problema de decision y al problema original se diferencian a lo sumo por un factor lineal Vease tambien EditarEntscheidungsproblemReferencias EditarWeisstein Eric W DecisionProblem Definicion En Weisstein Eric W ed MathWorld en ingles Wolfram Research Datos Q3262192 Obtenido de https es wikipedia org w index php title Problema de decision amp oldid 138777676, wikipedia, wiki, leyendo, leer, libro, biblioteca,
