パスワードを忘れた? アカウント作成
この議論は賞味期限が切れたので、アーカイブ化されています。 新たにコメントを付けることはできません。

P≠NP」記事へのコメント

  • by Anonymous Coward

    最後の、定理7から系8を導くところは自明ではないと思います。
    ある問題AがPに属することと、
    その問題Aを解く回路族[C]の回路経路の数が多項式規模に収まることが、
    必要十分条件であることの証明が必要に思います。

    #論理式「CVPq≠p(fix(p))=0」のパースが厳しいです。
    #「q≠pとなる任意のqについてCVPq(fix(p))=0」の意味でしょうか。

    • コメントありがとうございます。

      配線は全て元の回路のままですので、極小回路に独自の回路経路があれば、その回路経路上に独自の素子も存在します。
      ですので、独自の回路経路が多項式規模に収まらなければ素子も多項式規模に収まらないことになります。

      ただ、そちらではなくて定理6に間違いがありそうなので、ちょっと深堀しようかと思います。

      • by Anonymous Coward

        極小回路などの概念を正しく読み取れているかはわかりませんが
        回路経路は独自でも、独自の素子があるとは限らないのではないでしょうか。

        回路上の分岐と合流を単純化したものとして、以下のような回路を考えます。
          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
        のようになった場合、
        各回路経路は異なっていてそれぞれ独自であるものの、素子には独自のものは無い、
        ということにならないでしょうか。

        • by fiercewinds (22740) on 2017年08月24日 2時23分 (#3266421) 日記

          ふむ、グラフとしては経路のパターンが4種類ありますね。
          確かに証明が足りなさそうです。

          ざっと考えてみましたが、下記の方針でギャップを埋められそうです。
          このグラフはあくまで回路であることに注意すると、(x1が出力側だとして)x7の出力が0,1の2通りしか無いため、取りうる回路経路の組み合わせも2通りのみ。
          出力の種類を増やすには配線と素子を追加する必要があるので、結果として独自の素子が必要となる。

          ただ、やはり証明6に間違いがありましたので、そちらのほうが痛いですね……もっと回路の構造に踏み込む必要がありそうです。

          親コメント

Stay hungry, Stay foolish. -- Steven Paul Jobs

処理中...