Question

Morioka dans sa thèse de 2005 [1] référencé "Sur l'uniformité à l'intérieur $ Nc ^ 1 $" par Barrington, Immerman et Straubing. Utilisation de l'énoncé suivant:

Tous $ mathbf {nc ^ 1} $-Predicate est calculé par une famille de formules propositionnelles de taille polynomiale Dlogtime-Uniforme

Cette phrase est essentielle pour définir une réduction d'un $ mathbf {nc ^ 1} $ fonction au $ Sigma_1 ^ q $- Problème de tension pour $ G_0 $, cependant je ne suis pas en mesure de comprendre comment cette déclaration a été atteinte à partir du document d'origine, soit je manque quelque chose d'important ici, soit mon expertise dans la complexité des circuits ne suffit pas, quelqu'un peut-il intuitivement expliquer comment cette phrase est devenue?

Pas de solution correcte

Licencié sous: CC-BY-SA avec attribution
Non affilié à cs.stackexchange
scroll top