Pourquoi P et P / poly ne sont-ils pas trivialement les mêmes?

10

La définition de P est un langage qui peut être décidé par un algorithme de temps polynomial. La définition de P / poly peut être interprétée comme signifiant un langage qui peut être décidé par un circuit de taille polynomiale (voir http://pages.cs.wisc.edu/~jyc/02-810notes/lecture09.pdf ). Maintenant, pourquoi un circuit de taille polynomiale ne peut-il pas être simulé en temps polynomial?

dcw
la source
4
P / poly peut calculer des langages indécidables (exercice).
Yuval Filmus
Merci, mais qu'est-ce qui ne va pas avec mon argument - qu'un circuit de taille polynomiale peut être simulé en temps polynomial?
dcw
3
C'est faux. Les circuits de taille polynomiale pour différentes longueurs d'entrée peuvent être radicalement différents, et ne peuvent donc pas tous être décrits par une seule machine de Turing.
Yuval Filmus
Merci, mais où dans la définition P est-il dit que nous sommes limités à une seule machine Turing? Toutes les définitions que j'ai vues sont comme dans mathworld.wolfram.com/PolynomialTime.html
dcw
3
@dcw Une langue est en P s'il y a une machine Turing telle que ...
David Richerby

Réponses:

19

Le point sur les circuits est qu'un circuit a un nombre fixe d'entrées. Cela signifie que, pour définir un langage, nous avons besoin d'une famille de circuits C0,C1,C2, telle que le circuit  Ci vous indique quelles chaînes de longueur  i sont dans le langage, pour chaque  i . Cela n'exige pas qu'il y ait une relation entre les circuits Ci et  Ci+1 : ils pourraient être complètement différents. En particulier, pour tout ensemble  SN , vous pouvez définir déclarer Ci=true siiS etCi=false pouriS . Même siS  est indécidable!

En revanche, une langue est en  P s'il existe une seule machine de Turing qui vous indique si chaque entrée possible de chaque longueur possible est dans la langue. Maintenant, vous ne pouvez pas jouer à des jeux amusants sur des entrées de différentes longueurs.

Vous avez raison que nous pouvons évaluer tout circuit fixe  P . Mais cela ne suffit pas nécessairement pour décider d' une langue dans P/poly . Pour ce faire, nous devons d'abord calculer la longueur de l'entrée, puis l'utiliser pour déterminer le circuit  Ci nous devons évaluer, puis évaluer le circuit. Comme le montre l'exemple ci-dessus, la partie "déterminer quel circuit" pourrait même ne pas être calculable, et encore moins calculable en temps polynomial.

David Richerby
la source
1
P/poly