Explicação das classes P e NP através do cálculo lambda

36

Na introdução e explicação das classes de complexidade P e NP, muitas vezes dadas pela máquina de Turing. Um dos modelos de computação é o cálculo lambda. Entendo que todos os modelos de computação são equivalentes (e se podemos introduzir algo em termos de máquina de Turing, podemos introduzi-lo em termos de qualquer modelo de computação), mas nunca vi a ideia explicativa das classes de complexidade P e NP através do cálculo lambda . Alguém pode explicar as noções de complexidade P e NP sem a máquina de Turing e apenas com o cálculo lambda como modelo de computação.

Simplex
fonte
5
Seu poder computacional é equivalente apenas para funções sobre números naturais, não para tipos mais altos ou outras configurações.
Kaveh
Turing completude às vezes é um conceito mais teórica para mostrar uma conexão, mas mais aplicados "conversões" entre sistemas completos TM nem sempre são efectivamente realizadas na prática, ou seja, a sua às vezes mais sobre as provas de existência ...
vzn

Respostas:

40

Máquinas de Turing e λ cálculo são equivalentes apenas nas funções NN que podem definir.

Do ponto de vista da complexidade computacional, eles parecem se comportar de maneira diferente. A principal razão pela qual as pessoas usam máquinas de Turing e não o λ calcculus para raciocinar sobre a complexidade é que o uso do λ calcculus leva a medidas de complexidade irrealistas, porque você pode copiar termos (de tamanho arbitrário) livremente em etapas de redução β , por exemplo (λx.xxx)MMMM.Em outras palavras, etapas de redução única em λ-calculus são um péssimo modelo de custo. Por outro lado, as etapas de redução de uma máquina de Turing funcionam muito bem (no sentido de serem bons preditores do tempo de execução do programa no mundo real).

Não se sabe como recuperar completamente a teoria da complexidade convencional baseada em máquina de Turing no λ cálculo. Em uma recente descoberta (2014), Accattoli e Dal Lago conseguiram mostrar que grandes classes de complexidade de tempo, como P , NP e EXP podem receber uma formulação natural de cálcio- λ . Mas classes menores como O(n2) ou O(nlogn) não pode ser apresentado usando as técnicas Accattoli / Dal Lago.

Como recuperar a complexidade do espaço convencional usando o λ calcculus é desconhecido.

Martin Berger
fonte
4
Sinto a necessidade de esclarecer aqui: não existe uma "técnica" especial que Accattoli e Dal Lago usam para "apresentar" as aulas de tempo. A apresentação é a "ingênua": defina como a classe de idiomas decidível por um λ- termo nas etapas de redução f ( n ) β , sob qualquer estratégia de redução padrão ( por exemplo, à esquerda) -outermost). Accattoli e Dal Lago mostraram, usando técnicas provenientes da lógica linear, que existe um polinômio p tal que λ T I M E ( fλTEuME(f(n))λf(n) βp .λTEuME(f(n))=TEuME(p(f(n))
Damiano Mazza
@DamianoMazza Sim, está certo, o que eu quis dizer é que não acho que as técnicas usadas para mostrar esse resultado possam ser usadas para mostrar, por exemplo, . λTEuME(n2)=TEuME(n2)
Martin Berger
3
OK eu vejo. Na verdade, meu palpite é que : classes de complexidade como T I M E ( n 2 ) ou T I M E ( n log n ) não são robustas , não se pode esperar que eles sejam estáveis ​​sob as mudanças no modelo computacional (esse é notoriamente o caso, mesmo se continuarmos com as máquinas de Turing, por exemplo , fita única versus fita múltipla).λTIME(n2)TIME(n2)TIME(n2)TIME(nlogn)
Damiano Mazza
3
@DamianoMazza Eu concordo, da mesma forma com o tamanho do alfabeto escolhido. Mas um algoritmo executado em em uma máquina com fita n pode ser simulado em 5 k f 2 ( n ) em uma máquina com 1 fita, uma explosão quadrática modesta. Qual é a explosão da tradução atual de Accattoli e Dal Lago? Não me lembro se eles explicitam isso. f(n)n5kf2(n)
Martin Berger
1
@Jake O artigo citado discute a normalização beta (consulte a página dois). Resultados semelhantes já eram conhecidos por outras formas de redução, como redução fraca (ou seja, chamada por valor) - ver Dal Lago & Martini, 2008 (discutido nesse artigo e em cstheory.stackexchange.com/a/397/989 )
Blaisorblade 18/01/19
12

Eu colo parte de uma resposta que escrevi para outra pergunta :

A complexidade computacional implícita visa caracterizar classes de complexidade por meio de linguagens dedicadas. Os primeiros resultados, como o Teorema de Bellantoni-Cook, foram declarados em termos de funções recursivas, mas resultados mais recentes usam o vocabulário e as técnicas do λ- cálcio. Consulte esta breve introdução à complexidade computacional implícita para obter mais informações, ou os procedimentos dos workshops da DICE .μλ

Existem caracterizações de (pelo menos) por meio de λ -calculus.FPλ

Bruno
fonte
5

Não sei se isso responde (parte da) sua pergunta, mas existem de fato caracterizações alternativas das classes de complexidade (especialmente P e NP ) em termos de lógicas (lógica de 1ª ordem, lógica de 2ª ordem, etc.).

Por exemplo, o trabalho de R. Fagin (et al.) Nessa área é notável (e imo pode fornecer informações relacionadas ao problema P vs NP e às relações com complexidade descritiva e algorítmica )

Algumas caracterizações adicionais das classes de complexidade computacional em termos de complexidade algorítmica (Kolmogorov-Solomonov) podem ser encontradas (por exemplo) aqui e aqui .

Nikos M.
fonte