Clique的电路和公式

Question

说是说Clique问题在 $ p $ iff中存在一个boolean电路 $C $ 决定大小由多项式界限的Clique？并基于这个问题，这是否暗示存在等效的布尔公式<跨度类=“math-container”> $ f $ 来决定大小由多项式界限的Clique？如果存在这样的 $ f $ ，则基于来自 $ f的任何成员的命题逻辑公理存在正确的推导$ 到相应的 Clique的大天真公式

Answer 1

我担心所有问题的答案是假的：

• 有语言由恒定大小的电路决定，不可判定。
猜测 $ \ mathsf {nc ^ 1} \ neq \ mathsf {p} $ 。 它被猜测<跨越类=“math-container”> $ \ mathsf {np} \ neq \ mathsf {conp} $ 。