アカウント名:
パスワード:
最後の、定理7から系8を導くところは自明ではないと思います。ある問題AがPに属することと、その問題Aを解く回路族[C]の回路経路の数が多項式規模に収まることが、必要十分条件であることの証明が必要に思います。
#論理式「CVPq≠p(fix(p))=0」のパースが厳しいです。#「q≠pとなる任意のqについてCVPq(fix(p))=0」の意味でしょうか。
コメントありがとうございます。
配線は全て元の回路のままですので、極小回路に独自の回路経路があれば、その回路経路上に独自の素子も存在します。ですので、独自の回路経路が多項式規模に収まらなければ素子も多項式規模に収まらないことになります。
ただ、そちらではなくて定理6に間違いがありそうなので、ちょっと深堀しようかと思います。
極小回路などの概念を正しく読み取れているかはわかりませんが回路経路は独自でも、独自の素子があるとは限らないのではないでしょうか。
回路上の分岐と合流を単純化したものとして、以下のような回路を考えます。 x1 / \x2 x3 \ / x4 / \x5 x6 \ / x7
このとき、ある割当p1~p4についてのそれぞれの極小回路の独自回路経路が、もしも仮に p1: x1→x2→x4→x5→x7 p2: x1→x3→x4→x5→x7 p3: x1→x2→x4→x6→x7 p4: x1→x3→x4→x6→x7のようになった場合、各回路経路は異なっていてそれぞれ独自であるものの、素子には独自のものは無い、ということにならないでしょうか。
ふむ、グラフとしては経路のパターンが4種類ありますね。確かに証明が足りなさそうです。
ざっと考えてみましたが、下記の方針でギャップを埋められそうです。このグラフはあくまで回路であることに注意すると、(x1が出力側だとして)x7の出力が0,1の2通りしか無いため、取りうる回路経路の組み合わせも2通りのみ。出力の種類を増やすには配線と素子を追加する必要があるので、結果として独自の素子が必要となる。
ただ、やはり証明6に間違いがありましたので、そちらのほうが痛いですね……もっと回路の構造に踏み込む必要がありそうです。
より多くのコメントがこの議論にあるかもしれませんが、JavaScriptが有効ではない環境を使用している場合、クラシックなコメントシステム(D1)に設定を変更する必要があります。
Stay hungry, Stay foolish. -- Steven Paul Jobs
最後 (スコア:0)
最後の、定理7から系8を導くところは自明ではないと思います。
ある問題AがPに属することと、
その問題Aを解く回路族[C]の回路経路の数が多項式規模に収まることが、
必要十分条件であることの証明が必要に思います。
#論理式「CVPq≠p(fix(p))=0」のパースが厳しいです。
#「q≠pとなる任意のqについてCVPq(fix(p))=0」の意味でしょうか。
Re: (スコア:1)
コメントありがとうございます。
配線は全て元の回路のままですので、極小回路に独自の回路経路があれば、その回路経路上に独自の素子も存在します。
ですので、独自の回路経路が多項式規模に収まらなければ素子も多項式規模に収まらないことになります。
ただ、そちらではなくて定理6に間違いがありそうなので、ちょっと深堀しようかと思います。
Re: (スコア:0)
極小回路などの概念を正しく読み取れているかはわかりませんが
回路経路は独自でも、独自の素子があるとは限らないのではないでしょうか。
回路上の分岐と合流を単純化したものとして、以下のような回路を考えます。
x1
/ \
x2 x3
\ /
x4
/ \
x5 x6
\ /
x7
このとき、ある割当p1~p4についてのそれぞれの極小回路の独自回路経路が、もしも仮に
p1: x1→x2→x4→x5→x7
p2: x1→x3→x4→x5→x7
p3: x1→x2→x4→x6→x7
p4: x1→x3→x4→x6→x7
のようになった場合、
各回路経路は異なっていてそれぞれ独自であるものの、素子には独自のものは無い、
ということにならないでしょうか。
Re:最後 (スコア:1)
ふむ、グラフとしては経路のパターンが4種類ありますね。
確かに証明が足りなさそうです。
ざっと考えてみましたが、下記の方針でギャップを埋められそうです。
このグラフはあくまで回路であることに注意すると、(x1が出力側だとして)x7の出力が0,1の2通りしか無いため、取りうる回路経路の組み合わせも2通りのみ。
出力の種類を増やすには配線と素子を追加する必要があるので、結果として独自の素子が必要となる。
ただ、やはり証明6に間違いがありましたので、そちらのほうが痛いですね……もっと回路の構造に踏み込む必要がありそうです。