Circuits et formules pour la clique

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 ?

Answer 1

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} $ .