Explication des classes P et NP par lambda-calcul

Dans l'introduction et l'explication, les classes de complexité P et NP souvent données par la machine de Turing. L'un des modèles de calcul est le lambda-calcul. Je comprends que tous les modèles de calcul sont équivalents (et si nous pouvons introduire n'importe quoi en termes de machine de Turing, nous pouvons le présenter en termes de n'importe quel modèle de calcul), mais je n’ai jamais vu d’explication d’idée les classes de complexité P et NP à travers le lambda-calcul . Quelqu'un peut-il expliquer les notions de classes de complexité P et NP sans machine de Turing et uniquement avec le calcul lambda comme modèle de calcul?

cc.complexity-theory complexity-classes turing-machines lambda-calculus Simplex
la source

Leur puissance de calcul n’est équivalente que pour les fonctions sur des nombres naturels, et non pour des types plus élevés ou d’autres paramètres.

Kaveh

Turing complet est parfois un concept plus théorique pour montrer une connexion mais plus qu'appliqué « conversions » entre TM systèmes complets ne sont pas toujours effectivement mises en pratique par exemple son parfois plus sur les preuves d'existence ...

VZN

Réponses:

Les machines de Turing et $\lambda$ -calcul ne sont équivalentes que par les fonctions $\mathbb{N} \rightarrow \mathbb{N}$ qu'elles peuvent définir.

Du point de vue de la complexité informatique, ils semblent se comporter différemment. La raison principale pour laquelle les gens utilisent les machines de Turing et non pas $\lambda$ calcul pour raisonner sur la complexité est que l'utilisation de $\lambda$ calculus conduit naïvement à des mesures de complexité irréalistes, car vous pouvez copier des termes (de taille arbitraire) librement dans des étapes de $\beta$ réduction, par exemple $(\lambda x.xxx)M \rightarrow MMM.$ En d'autres termes, les étapes de réduction simples dans $\lambda$ -calcul sont un modèle de coût moche. En revanche, les étapes simples de réduction de la machine de Turing fonctionnent très bien (en ce sens qu’elles sont de bons prédicteurs de l’exécution d’un programme dans le monde réel).

On ne sait pas comment récupérer complètement la théorie classique de la complexité basée sur la machine de Turing dans le calcul- $\lambda$ . Lors d'une récente percée (2014), Accattoli et Dal Lago ont réussi à montrer que de grandes classes de complexité temporelle telles que $P$ , $NP$ et $EXP$ peuvent recevoir une formulation naturelle de $\lambda$ calcul. Mais des classes plus petites comme $O(n^2)$ ou $O(n \, log\, n)$ ne peut pas être présenté en utilisant les techniques Accattoli / Dal Lago.

Comment récupérer la complexité de l'espace conventionnel à l'aide de $\lambda$ -calculus est inconnu.

Martin Berger
la source

Je ressens le besoin de clarifier ici: il n’ya pas de "technique" particulière utilisée par Accattoli et Dal Lago pour "présenter" des classes de temps. La présentation est le « naïf » une: définir

comme la classe des langages décidables par un

-terme dans

-Réduction étapes, en vertu d' une stratégie de réduction standard ( par exemple à gauche plus externe). Accattoli et Dal Lago ont montré, à l'aide de techniques issues de la logique linéaire, qu'il existe un polynôme

tel 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 Oui, c'est ce que je voulais dire. Je ne pense pas que les techniques utilisées pour montrer ce résultat puissent être utilisées pour montrer, par exemple,

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

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

Martin Berger

OK je vois. En fait, je suppose que

: classes de complexité tels que

ne sont pas robustes , on ne peut pas s’attendre à ce qu’ils soient stables face aux modifications apportées au modèle informatique (c’est notoirement le cas même si nous nous en tenons aux machines de Turing, par exemple une bande unique ou une bande multiple).

λ 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 Je suis d'accord, également pour la taille de l'alphabet choisi. Mais un algorithme fonctionnant dans

sur une machine à bandes

peut être simulé dans

sur une machine à bandes, une modeste explosion quadratique. Quelle est l'explosion de la traduction actuelle de Accattoli et Dal Lago? Je ne me souviens pas s'ils le disent explicitement.

f (n)

$f(n)$

n

$n$

5 k f^{2} (n)

$5kf^2(n)$

Martin Berger

@Jake L'article cité traite de la normalisation bêta (voir page deux). Des résultats similaires étaient déjà connus pour d'autres formes de réduction, telles que la réduction faible (c'est-à-dire, call-by-value) - voir Dal Lago & Martini, 2008 (discuté dans cet article et dans cstheory.stackexchange.com/a/397/989 ).

Blaisorblade

Je colle une partie de la réponse que j'ai écrite pour une autre question :

La complexité informatique implicite vise à caractériser les classes de complexité au moyen de langages dédiés. Les premiers résultats tels que le théorème de Bellantoni-Cook ont été énoncés en termes de fonctions récursives, mais des résultats plus récents utilisent le vocabulaire et les techniques de -calculus. Voir cette brève introduction à la complexité de calcul implicite pour plus d'informations et d'indicateurs, ou pour consulter les débats des ateliers DICE . $\mu$ $\lambda$

Il existe des caractérisations de (au moins) au moyen de -calcul. $\mathsf{FP}$ $\lambda$

Bruno
la source

Je ne sais pas si cela répond (en partie) à votre question, mais il existe effectivement des caractérisations alternatives des classes de complexité (en particulier $\mathbb{P}$ et $\mathbb{NP}$ ) en termes de logique (logique du 1er ordre, logique du 2ème ordre, etc.).

Par exemple, les travaux de R. Fagin (et al.) Dans ce domaine sont remarquables (et l’imo pourrait donner un aperçu du problème $\mathbb{P}$ vs $\mathbb{NP}$ et des relations avec complexité algorithmique ).

Certaines caractérisations supplémentaires des classes de complexité de calcul en termes de complexité algorithmique (Kolmogorov-Solomonov) peuvent être trouvées (par exemple) ici et ici .

Nikos M.
la source