Explicación de las clases P y NP a través del cálculo lambda

En la introducción y explicación, las clases de complejidad P y NP a menudo se dan a través de la máquina Turing. Uno de los modelos de computación es el cálculo lambda. Entiendo que todos los modelos de computación son equivalentes (y si podemos introducir algo en términos de máquina de Turing, podemos introducir esto en términos de cualquier modelo de computación), pero nunca vi la idea de explicación de las clases de complejidad P y NP a través del cálculo lambda . ¿Alguien puede explicar las nociones de clases de complejidad P y NP sin la máquina de Turing y solo con el cálculo lambda como modelo de cálculo?

cc.complexity-theory complexity-classes turing-machines lambda-calculus Simplex
fuente

Su poder computacional es equivalente solo para funciones sobre números naturales, no para tipos más altos u otras configuraciones.

Kaveh

Turing completo es a veces un concepto más teórico para mostrar una conexión, pero más en su aplicación "conversiones" entre sistemas completos TM no están siempre en realidad llevado a cabo en la práctica, es decir, su a veces más sobre las pruebas de existencia ...

VZN

Respuestas:

Las máquinas de Turing y el cálculo de $\lambda$ son equivalentes solo con las funciones $\mathbb{N} \rightarrow \mathbb{N}$ que pueden definir.

Desde el punto de vista de la complejidad computacional, parecen comportarse de manera diferente. La razón principal por la que las personas usan máquinas de Turing y no el cálculo de $\lambda$ para razonar sobre la complejidad es que usar el cálculo de $\lambda$ ingenuamente conduce a medidas de complejidad poco realistas, porque puede copiar términos (de tamaño arbitrario) libremente en pasos de reducción de $\beta$ únicos , por ejemplo $(\lambda x.xxx)M \rightarrow MMM.$ En otras palabras, pasos de reducción individuales en $\lambda$ -el cálculo es un modelo de pésimo costo. Por el contrario, los pasos de reducción de una sola máquina de Turing funcionan muy bien (en el sentido de ser buenos predictores del tiempo de ejecución del programa del mundo real).

No se sabe cómo recuperar completamente la teoría convencional de la complejidad basada en la máquina de Turing en el cálculo $\lambda$ . En un reciente avance (2014), Accattoli y Dal Lago lograron demostrar que a grandes clases de complejidad temporal como $P$ , $NP$ y $EXP$ se les puede dar una formulación natural de cálculo $\lambda$ . Pero clases más pequeñas como $O(n^2)$ u $O(n \, log\, n)$ no puede presentarse utilizando las técnicas Accattoli / Dal Lago.

Se desconoce cómo recuperar la complejidad espacial convencional utilizando el cálculo $\lambda$ .

Martin Berger
fuente

Siento la necesidad de aclarar aquí: no hay una "técnica" especial que Accattoli y Dal Lago usen para "presentar" las clases de tiempo. La presentación es la "ingenua": defina

como la clase de lenguajes decidible por un término

en los pasos de reducción

, bajo cualquier estrategia de reducción estándar ( por ejemplo, el extremo izquierdo -más exterior). Accattoli y Dal Lago demostraron, usando técnicas que provienen de la lógica lineal, que hay un polinomio

tal que

λ T I M E (f (n))

$\lambda TIME(f(n))$

λ

$\lambda$

f (n)

$f(n)$

β

$\beta$

p

$p$

λ T I M E (f (n)) = T I M E (p (f (n))

$\lambda TIME(f(n))=TIME(p(f(n))$

Damiano Mazza

@DamianoMazza Sí, es cierto, lo que quise decir es que no creo que las técnicas utilizadas para mostrar este resultado puedan usarse, por ejemplo, para mostrar

λ T I M E (n^{2}) = T I M E (n^{2})

$\lambda TIME(n^2) = TIME(n^2)$

Martin Berger

OK veo. En realidad, supongo que

: las clases de complejidad como

no son robustas , uno no puede esperar que sean estables bajo los cambios en el modelo computacional (este es notoriamente el caso incluso si nos limitamos a las máquinas de Turing, por ejemplo , una sola cinta versus varias cintas).

λ T I M E (n^{2}) \neq T I M E (n^{2})

$\lambda TIME(n^2)\neq TIME(n^2)$

T I M E (n^{2})

$TIME(n^2)$

T I M E (n \log n)

$TIME(n\log n)$

Damiano Mazza

@DamianoMazza Estoy de acuerdo, del mismo modo para el tamaño del alfabeto elegido. Pero un algoritmo que se ejecuta en

en una máquina de

cintas puede simularse en

en una máquina de 1 cinta, una modesta explosión cuadrática. ¿Cuál es la explosión de la traducción actual de Accattoli y Dal Lago's? No recuerdo si lo declaran explícitamente.

f (n)

$f(n)$

n

$n$

5 k f^{2} (n)

$5kf^2(n)$

Martin Berger

@Jake El artículo citado analiza la normalización beta (consulte la página dos). Ya se conocían resultados similares para otras formas de reducción, como la reducción débil (es decir, llamada por valor): ver Dal Lago y Martini, 2008 (discutido en ese documento y en cstheory.stackexchange.com/a/397/989 )

Blaisorblade

Pego parte de una respuesta que escribí para otra pregunta :

La complejidad computacional implícita tiene como objetivo caracterizar las clases de complejidad mediante lenguajes dedicados. Los primeros resultados, como el Teorema de Bellantoni-Cook, se expresaron en términos de funciones recursivas , pero los resultados más recientes utilizan el vocabulario y las técnicas de cálculo . Consulte esta breve introducción a la complejidad computacional implícita para obtener más información y sugerencias, o las actas de los talleres DICE . $\mu$ $\lambda$

Existen caracterizaciones de (al menos) por medio de cálculo . $\mathsf{FP}$ $\lambda$

Bruno
fuente

No sé si esto responde (parte de) su pregunta, pero de hecho hay caracterizaciones alternativas de las clases de complejidad (especialmente $\mathbb{P}$ y $\mathbb{NP}$ ) en términos de lógica (lógica de primer orden, lógica de segundo orden, etc.).

Por ejemplo, el trabajo de R. Fagin (et al.) En esta área es notable (e imo podría proporcionar información relacionada con el tema $\mathbb{P}$ vs $\mathbb{NP}$ y las relaciones con la complejidad descriptiva y algorítmica )

Se pueden encontrar algunas caracterizaciones adicionales de las clases de complejidad computacional en términos de complejidad algorítmica (Kolmogorov-Solomonov) (por ejemplo) aquí y aquí .

Nikos M.
fuente