¿Cuál es la diferencia entre un algoritmo, un idioma y un problema?

Parece que en este sitio, las personas a menudo corrigen a otros por "algoritmos" y "problemas" confusos. ¿Cuál es la diferencia entre estos? ¿Cómo sé cuándo debería considerar algoritmos y problemas? ¿Y cómo se relacionan con el concepto de lenguaje en la teoría del lenguaje formal?

Para simplificar, comenzaré considerando solo los problemas de "decisión", que tienen una respuesta sí / no. Los problemas de función funcionan aproximadamente de la misma manera, excepto que en lugar de sí / no, hay una palabra de salida específica asociada con cada palabra de entrada.

Idioma : un idioma es simplemente un conjunto de cadenas. Si tiene un alfabeto, como , entonces Σ ∗ es el conjunto de todas las palabras que contienen solo los símbolos en Σ . Por ejemplo, { 0 , 1 } ∗ es el conjunto de todas las secuencias binarias de cualquier longitud. Sin embargo, un alfabeto no necesita ser binario. Puede ser unario, ternario, etc.$\Sigma$$\Sigma^*$$\Sigma$$\{0,1 \}^*$

Un idioma sobre un alfabeto es cualquier subconjunto de Σ ∗ .$\Sigma$$\Sigma^*$

Problema : Un problema es una pregunta sobre alguna entrada que nos gustaría responder. Específicamente, un problema de decisión es una pregunta que pregunta: "¿Nuestra entrada dada cumple con la propiedad ?$X$

Un lenguaje es la realización formal de un problema. Cuando queremos razonar teóricamente sobre un problema de decisión, a menudo examinamos el lenguaje correspondiente. Para un problema , el idioma correspondiente es:$X$

es la codificación de una entrada y para el problema X , y la respuesta a la entrada y para el problema X es "Sí" $L = \{w \mid w$$y$$X$$y$$X$$\}$

Determinar si la respuesta para una entrada a un problema de decisión es "sí" es equivalente a determinar si una codificación de esa entrada sobre un alfabeto está en el idioma correspondiente.

Algoritmo : un algoritmo es una forma paso a paso para resolver un problema. Tenga en cuenta que un algoritmo puede expresarse de muchas maneras y en muchos idiomas, y que hay muchos algoritmos diferentes para resolver cualquier problema.

Máquina de Turing : una máquina de Turing es el análogo formal de un algoritmo. Una máquina de Turing sobre un alfabeto dado, para cada palabra, se detendrá o no en un estado de aceptación. Por lo tanto, para cada máquina de Turing , hay un lenguaje correspondiente:$M$

detiene en un estado de aceptación en la entrada w } .$L(M) = \{w \mid M$$w\}$

(Hay una sutil diferencia entre las máquinas Turing que se detienen en todas las entradas y las entradas sí, lo que define la diferencia entre las clases de complejidad y R E ).$\mathsf{R}$$\mathsf{RE}$

La relación entre los idiomas y las máquinas de Turing es la siguiente

1. Cada máquina de Turing acepta exactamente un idioma

2. Puede haber más de una máquina de Turing que acepte un idioma determinado

3. Es posible que no haya una máquina de Turing que acepte un idioma determinado.

Podemos decir más o menos lo mismo sobre los algoritmos y problemas: cada algoritmo resuelve un solo problema, pero puede haber 0, o muchos, algoritmos que resuelvan un problema dado.

Complejidad del tiempo : una de las fuentes más comunes de confusión entre algoritmos y problemas se refiere a las clases de complejidad. La asignación correcta se puede resumir de la siguiente manera:

• Un algoritmo tiene una complejidad temporal.
• Un problema pertenece a una clase de complejidad.

Un algoritmo puede tener una cierta complejidad de tiempo. Decimos que un algoritmo tiene una complejidad de límite superior en el peor de los casos si el algoritmo se detiene en la mayoría de los pasos f ( n ) para cualquier entrada de tamaño n .$f(n)$$f(n)$$n$

Los problemas no tienen tiempos de ejecución, ya que un problema no está vinculado a un algoritmo específico que realmente se ejecuta. En cambio, decimos que un problema pertenece a una clase de complejidad, si existe algún algoritmo que resuelva ese problema con una complejidad de tiempo dada.

etc. son todas clases de complejidad. Esto significa que contienen problemas, no algoritmos. Un algoritmo nunca puede estar en P , pero si hay un algoritmo de tiempo polinómico para resolver un problema dado X , entonces X está en P . También podría haber un montón de algoritmos en tiempo exponencial aceptar X , pero ya que no existe un único algoritmo de tiempo polinomial aceptar X , que está en P .$\mathsf{P}, \mathsf{NP}, \mathsf{PSPACE}, \mathsf{EXPTIME}$$\mathsf{P}$$X$$X$$\mathsf{P}$$X$$X$$\mathsf{P}$