クリークのための回路と式

Question

クリークの問題が $ p $ のIFFにあると言うのは、ブール回路のファミリが存在する $サイズが多項式によって制限されているクリークを決定するためのC $ そしてこの質問そのサイズが多項式によって制限されているクリークを決定するために、同等のブール式の形式の組具が存在することを意味しますか？ $ f $ ？そして、そのような $ f $ がある場合、 $ fの任意のメンバーからの命題論理公理に基づく正しい派生があるでしょうか。対応する CLIQUE ？

Answer 1

あなたのすべての質問に対する答えが偽のことを恐れています：

• 決められない一定のサイズの回路で決定された言語があります。
• $ \ mathsf {nc ^ 1} \ neq \ mathsf {p} $ です。
• $ \ mathsf {np} \ neq \ mathsf {conp} $ 。