Problema de decisión

Problema de decisión

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 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?

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.

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 para en un tiempo finito al procesar esa entrada.

Los problemas de decisión son interesantes dado que todos los problemas 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.

Véase también

Referencias

Obtenido de "Problema de decisi%C3%B3n"

Wikimedia foundation. 2010.

См. также в других словарях:

  • Problema de decisión — En 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 la respuestas posibles son SI o NO. Un ejemplo típico de… …   Enciclopedia Universal

  • Problema abstracto — Saltar a navegación, búsqueda En ciencia computacional teórica, un problema abstracto o problema computacional es una relación entre un conjunto de instancias y un conjunto de soluciones. Un problema abstracto permite establecer formalmente la… …   Wikipedia Español

  • Problema de satisfacibilidad booleana — Saltar a navegación, búsqueda En teoría de la complejidad computacional, el Problema de satisfacibilidad booleana (SAT) fue el primer problema identificado como perteneciente a la clase de complejidad NP completo. Se trata de un problema donde… …   Wikipedia Español

  • Problema de la suma de subconjuntos — Saltar a navegación, búsqueda El problema de la suma de subconjuntos es un problema importante en la teoría de la complejidad y en la criptografía. El problema es este: dado un conjunto de enteros, ¿existe algún subconjunto cuya suma sea… …   Wikipedia Español

  • Problema de la cobertura de vértices — Saltar a navegación, búsqueda En ciencias de la computación, el Problema de la cobertura de vértices es un problema NP completo, que pertenece a los 21 problemas NP completos de Karp. Es muy utilizado en teoría de complejidad computacional para… …   Wikipedia Español

  • Problema de correspondencia de Post — Saltar a navegación, búsqueda El Problema de Correspondencia de Post es un problema de decisión indecidible que fue propuesto por Emil Post. Por ser más sencillo que el Problema de parada y que el Entscheidungsproblem, resulta útil para realizar… …   Wikipedia Español

  • Decisión — Saltar a navegación, búsqueda Para el álbum del grupo de hip hop chileno Tiro de Gracia, véase Decisión (álbum). Una decisión es el producto final del proceso mental cognitivo específico de un individuo o un grupo de personas u organizaciones, el …   Wikipedia Español

  • Problema de la partición — Saltar a navegación, búsqueda En ciencias de la computación, el Problema de la partición es un problema NP completo, que visto como un problema de decisión, consiste en decidir si, dado un multiconjunto de números enteros, puede éste ser… …   Wikipedia Español

  • Problema de isomorfismo de subgrafos — Saltar a navegación, búsqueda En complejidad computacional, el Problema de isomorfismo de subgrafos, también a veces llamado Problema de matching de subgrafos, es un problema de decisión NP completo, que formalmente, se define de la siguiente… …   Wikipedia Español

  • Problema de la clique — Saltar a navegación, búsqueda En complejidad computacional, el problema de la Clique o problema de la liga de amigos es un problema NP completo según la Teoría de la complejidad computacional. Una clique en un grafo es un conjunto de vértices dos …   Wikipedia Español


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»