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

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.

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

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:

Máquinas de Turing e $\lambda$ cálculo são equivalentes apenas nas funções $\mathbb{N} \rightarrow \mathbb{N}$ 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 $\lambda$ calcculus para raciocinar sobre a complexidade é que o uso do $\lambda$ calcculus leva a medidas de complexidade irrealistas, porque você pode copiar termos (de tamanho arbitrário) livremente em etapas de redução $\beta$ , por exemplo $(\lambda x.xxx)M \rightarrow MMM.$ Em outras palavras, etapas de redução única em $\lambda$ -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 $\lambda$ 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- $\lambda$ . Mas classes menores como $O(n^2)$ ou $O(n \, log\, n)$ não pode ser apresentado usando as técnicas Accattoli / Dal Lago.

Como recuperar a complexidade do espaço convencional usando o $\lambda$ calcculus é desconhecido.

Martin Berger
fonte

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

, 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

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

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

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

Martin Berger

OK eu vejo. Na verdade, meu palpite é que

: classes de complexidade como

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).

λ 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 Eu concordo, da mesma forma com o tamanho do alfabeto escolhido. Mas um algoritmo executado em

em uma máquina com fita

pode ser simulado em

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)

$f(n)$

n

$n$

5 k f^{2} (n)

$5kf^2(n)$

Martin Berger

@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

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 . $\mu$ $\lambda$

Existem caracterizações de (pelo menos) por meio de -calculus. $\mathsf{FP}$ $\lambda$

Bruno
fonte

Não sei se isso responde (parte da) sua pergunta, mas existem de fato caracterizações alternativas das classes de complexidade (especialmente $\mathbb{P}$ e $\mathbb{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 $\mathbb{P}$ vs $\mathbb{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