Circuits et formules pour la clique
-
29-09-2020 - |
Question
est-il correct de dire que le problème de la clique est dans $ p $ IFF existe une famille de circuits booléens $C $ Pour décider de la clique dont les tailles sont délimitées par un polynôme?Et basé sur Cette question ,Est-ce que cela implique qu'il existe un ensemble équivalent de formules booléennes $ f $ pour décider de la clique dont les tailles sont délimitées par un polynôme?Et s'il y a une telle classe $ f $ , serait-il correctement dérivés basé sur des axiomes logiques propositionnels de tout membre de $ f$ au Grande formule naïve pour la clique ?
La solution
J'ai bien peur que la réponse à toutes vos questions soit fausse:
- Il y a des langues décidées par des circuits de taille constante qui ne sont pas décrits.
- Il est conjecturé que $ \ mathsf {nc ^ 1} \ neq \ mathsf {p} $ . .
- Il est conjecturé que $ \ MATHSF {NP} \ NEQ \ MATHSF {CONP} $ .
Licencié sous: CC-BY-SA avec attribution
Non affilié à cs.stackexchange