Caractérisation logique de $ nc ^ 1 $
-
05-11-2019 - |
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