P / poly est la classe de problèmes de décision pouvant être résolus par une famille de circuits booléens de taille polynomiale. Il peut également être défini comme une machine de Turing à temps polynomial qui reçoit une chaîne de conseils de taille polynomiale en n et basée uniquement sur la taille de n.
Le mP / poly est la classe de problèmes de décision pouvant être résolus par une famille de circuits booléens monotones de taille polynomiale, mais existe-t-il une définition alternative naturelle du mP / poly en termes de machine de Turing à temps polynomial?
cc.complexity-theory
complexity-classes
circuit-complexity
polynomial-time
monotone
Jesse Stern
la source
la source
Réponses:
Il y a une notion de machine de Turing monotone non déterministe et, plus généralement, alternée dans le papier Monotone Complexity de Grigni et Sipser. Puisque le temps polynomial est le même que l'espace logarithmique alternatif, une caractérisation machine de uniforme est la machine de Turing à espace journal alterné monotone. Fournir une telle machine avec des conseils polynomiaux donnera alors une définition de machine de m P / p o l y .m P m P / p o l y
la source
Il existe en fait une notion de machine de Turing déterministe positive qui correspond à mP / Poly. Il peut être trouvé dans l'article Versions positives du temps polynomial de Lauteman, Schwentick et Stewart
la source