アカウント名:
パスワード:
>定理3>NNF回路には、入力が少なくとも(対応する)差分ベクトルの始点・終点のどちらか片方を含む時のみに1になるAND素子が存在する。つまり、NNF回路は問題の差分ベクトル毎にAND素子が必要となる。
差分ベクトルの個数=そのようなAND素子の個数という部分が証明できているようには全く見えないのですが。(思い込んでいるようには見えるけど。)
Pに属する問題であっても多項式規模の回路では解けないという証明になっちゃってませんか?
コメントありがとうございます。返事遅くなりすみません。
ご指摘の点、確かに証明が甘そうですね。証明を厳密化してみます。
より多くのコメントがこの議論にあるかもしれませんが、JavaScriptが有効ではない環境を使用している場合、クラシックなコメントシステム(D1)に設定を変更する必要があります。
私は悩みをリストアップし始めたが、そのあまりの長さにいやけがさし、何も考えないことにした。-- Robert C. Pike
真面目に読む気はないんだけれど (スコア:0)
>定理3
>NNF回路には、入力が少なくとも(対応する)差分ベクトルの始点・終点のどちらか片方を含む時のみに1になるAND素子が存在する。つまり、NNF回路は問題の差分ベクトル毎にAND素子が必要となる。
差分ベクトルの個数=そのようなAND素子の個数
という部分が証明できているようには全く見えないのですが。(思い込んでいるようには見えるけど。)
Pに属する問題であっても多項式規模の回路では解けないという証明になっちゃってませんか?
Re:真面目に読む気はないんだけれど (スコア:1)
コメントありがとうございます。
返事遅くなりすみません。
ご指摘の点、確かに証明が甘そうですね。
証明を厳密化してみます。