¿Por qué usar idiomas en la teoría de la complejidad?

Estoy empezando a entrar en la teoría de la computación, que estudia qué se puede calcular, qué tan rápido, usando cuánta memoria y con qué modelo computacional.

Tengo una pregunta bastante básica, pero realmente espero que algunos de ustedes puedan ayudarme a comprender el concepto detrás de esto:

¿Por qué todo se centra en la noción y definición de IDIOMAS (es decir, lenguajes regulares e idiomas libres de contexto)? ¿Y cómo se relacionan y describen la complejidad de un algoritmo y los posibles modelos computacionales para resolverlos?

Leí este tipo de preguntas relacionadas:

• /cstheory/14811/what-is-the-enlightenment-im-supposed-to-attain-after-studying-finite-automata
• /cstheory/8539/how-practical-is-automata-theory

pero aún no tengo una respuesta a mis dudas, ya que proporcionan una justificación práctica de por qué son importantes (lo que sí entiendo) pero no me ayudan a entender por qué la teoría de la complejidad se basa en ellas.

Es porque los idiomas son la mejor (¿única?) Forma de formalizar el concepto de "problema".

Un algoritmo (Turing Machine) tiene un rendimiento que expresamos a través de la complejidad big-O. Un problema (lenguaje) pertenece a una clase de complejidad. Estos generalmente se definen por la existencia: si existe una máquina que acepta un lenguaje que se ejecuta en un rendimiento dado (espacio o tiempo), entonces el lenguaje pertenece a la clase de complejidad correspondiente.$L$

Hay algunas razones para esto. Primero es que los idiomas son independientes de la plataforma. No le preocupa si un número entero es de 32 o 64 bits, o si las operaciones de punto flotante se ejecutan en paralelo con otras operaciones. Estas cosas aceleran el rendimiento a nivel micro, pero el análisis de complejidad está interesado en el nivel macro. A medida que escala de 100 a a a entradas, ¿cómo cambia el rendimiento del algoritmo? ¿Va de usar 1 millón de celdas de cinta a mil millones, o de 1 millón a más células de las que hay átomos en el universo?10 9 10 $10^6$$10^9$$10^{12}$

El segundo es que los idiomas son solo una buena abstracción para los datos. Necesita algo sobre lo que pueda hacer pruebas, algo que pueda modelar formalmente. Codificar su entrada y salida como una cadena significa que ahora no está tratando con bits en la memoria, sino con objetos matemáticos con propiedades específicas. Puede razonar sobre ellos y probar pruebas sobre ellos en un sentido formal y muy simple.

La teoría de la complejidad tiende a centrarse en los problemas de decisión porque terminan siendo difíciles. Cuando la versión de decisión del vendedor ambulante es NP-complete (es decir, si hay un recorrido más corto que la longitud ), entonces, obviamente, encontrar el camino más corto es más difícil. No hay tanto enfoque en los problemas de función / optimización porque todavía hay muchas preguntas abiertas y problemas sin resolver sobre los problemas de decisión más simples.$k$

Creo que este es mi desafío para usted: encontrar la manera de describir matemáticamente problemas que no sean idiomas. No sé si los idiomas son especiales, pero creo que son la herramienta más simple que tenemos, la más fácil de manejar.

Hay dos respuestas básicas a su pregunta:

1. Hay más en la teoría de la complejidad que los lenguajes, por ejemplo, clases de funciones, complejidad aritmética y las subáreas de algoritmos de aproximación e inaproximabilidad.

2. Razones históricas: uno de los documentos básicos en la teoría de la computabilidad fue discutir el problema Entscheidungsproblem de Hilbert (una forma del problema de detención).

Lamentablemente, no sé mucho acerca de lo último, pero permítanme expandirme sobre lo primero.

Complejidad más allá de los idiomas.

Cada clase de complejidad computacional viene con una clase de función asociada . Por ejemplo, la clase P de todos los problemas decidibles en tiempo polinómico está asociada con FP, la clase de todas las funciones computables en tiempo polinómico. FP es importante, ya que se utiliza para definir NP-hard: un lenguaje es NP-difícil si para cada idioma en NP hay una función en FP tal que si y sólo si . Otra clase de complejidad de funciones, #P , está relacionada con la llamada jerarquía polinómica a través del teorema de Toda .M f M x ∈ M f M ( x ) ∈ $L$$M$$f_M$$x \in M$$f_M(x) \in L$

La complejidad del circuito aritmético (o teoría de la complejidad algebraica ) se ocupa de la complejidad de calcular varios polinomios. Las clases de complejidad importantes aquí son VP y VNP, y la teoría de la complejidad geométrica es un proyecto importante que intenta separar VP y VNP (y más tarde P y NP) utilizando geometría algebraica y teoría de representación.

Otro ejemplo importante de complejidad algebraica es la multiplicación rápida de matrices. Aquí la pregunta básica es ¿qué tan rápido podemos multiplicar dos matrices ? Preguntas similares preguntan qué tan rápido podemos multiplicar enteros, qué tan rápido podemos probar los enteros para primalidad (¡esto es un problema de decisión!) Y qué tan rápido podemos factorizar enteros.

La optimización convexa se ocupa de los problemas de optimización que pueden resolverse (o casi resolverse) de manera eficiente. Ejemplos son la programación lineal y la programación semidefinida, las cuales tienen algoritmos eficientes. Aquí estamos interesados ​​tanto en la solución óptima como en la solución óptima. Como a menudo hay más de una solución óptima, calcular una solución óptima no está bien representado como un problema de decisión.

La aproximabilidad es el área que estudia qué tan buena es la aproximación que podemos obtener para un problema de optimización en tiempo polinómico. Considere, por ejemplo, el problema clásico de Set Cover: dada una colección de sets, ¿cuántos de ellos necesitamos para cubrir todo el universo? Encontrar el número óptimo es NP-hard, pero ¿tal vez sea posible calcular una aproximación? Los algoritmos de aproximación son los algoritmos de estudio de subárea para calcular las aproximaciones, mientras que la inaproximidad estudia los límites de los algoritmos de aproximación. En el caso particular de Set Cover, tenemos un algoritmo que da una aproximación (el algoritmo codicioso), y es NP-difícil mejorarlo.$\ln n$

Miremos esta pregunta desde la perspectiva de la teoría de categorías. Los problemas de decisión (o lenguajes) corresponderían a los objetos de una categoría, y las reducciones permitidas entre dos problemas corresponderían a los morfismos (flechas) de una categoría.

Hablar de idiomas tiene la ventaja de que la equivalencia de idiomas está bien definida (es decir, por igualdad extensional). Dos problemas no relacionados pueden conducir al mismo idioma, y ​​luego se nos permite considerarlos como equivalentes. Si quisiéramos hablar sobre problemas isomórficos, tendríamos que definir los morfismos permitidos entre dos problemas. Pero los morfismos permitidos dependen de la clase de complejidad real en consideración, lo que hace que este enfoque sea menos adecuado para comparar diferentes clases de complejidad.

La noción de problemas isomórficos normalmente será más gruesa que la noción de lenguajes equivalentes, es decir, dos problemas pueden ser isomórficos, incluso si sus lenguajes asociados no son equivalentes. Lo que es peor es que a menudo hay diferentes nociones razonables para los morfismos permitidos, que solo concuerdan con respecto a los isomorfismos permitidos. Centrarse en los idiomas permite posponer tales problemas hasta que tengamos ganas de hablar sobre algunas nociones razonables diferentes de reducción (como la reducción de Karp frente a la reducción de Cook).