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

/.Jに聞け:【助けて】 P≠NPの証明、これで合ってる?」記事へのコメント

  • func_a(x) : 判定問題Aを入力の長さの多項式時間以内に判定できる関数
    func_b(x) : 判定問題Bを(ry

    func_a_or_b (x) {
        return func_a(x) || func_b(x);
    }
    「AまたはB」の判定問題を解く多項式時間アルゴリズムが完成した!!1!
    (多項式を2つ加えても明らかに多項式のままだから、と一応念のため)

    あと、ついでに。
    > P問題とその論理和・否定を組み合わせることによって任意の論理式を構成することができる。
    その論理式のサイズが、入力長の多項式を超えるのなら、もはやPに含まれるかは定かではない。

    • コメントありがとう。
      >「AまたはB」の判定問題を解く多項式時間アルゴリズムが完成した!!1!

      そう。ここがこの証明の肝の部分ね。

      組み合わせの回数が多項式回数(定数回数かな?)の範囲なら確かに多項式時間アルゴリズムに収まるけど、この操作自体は「回数を制限していない」(指数回数でもOK)ので、多項式時間アルゴリズムになるとは限りません。
      実際「AまたはB」の判定問題もまたP問題だから、他のP問題C,D,E……と組み合わせて数多くの問題を作ることができます。
      (組み合わせ爆発ですな)

      またこの組み合わせで任意の回路が構

      • by Anonymous Coward

        色々つっこみたいのは山々なのだが、めんどいので一点だけ。
        この論法に、PとNPの代わりにPSPACE (決定性多項式空間) と NPSPACE (非決定性多項式空間) をぶち込んだらどうなる?
        それでもし PSPACE != NPSPACE になるのなら、とりあえず計算複雑性理論を頭から全部学びなおすとよいと思う。

        • そうそう。それが厄介な部分。
          この手法だとPSPACE≠NPSPACEで分離できちゃうんだよね。
          手法の切れ味が良すぎてSAVITCHの定理と矛盾してしまうという……

          ただ、この証明自体はチューリングマシン&回路族の計算モデルと集合論の理論しか使っていないので、この証明が矛盾を抱えているというのも考えにくい。

          まあ、P≠NPならば中間領域の問題クラスの存在も示されているので、この結果はその一つの表れなのかもしれません。最悪、(SAVITCHの定理が公理としている)漸近的解析による複雑性クラスがチューリングマシン・回路計算量のモデルと矛盾しているという可能性もありますが、それは引き続き研究しないと結論付けできないと思います。

          • SAVITCHの定理は
             NSPACE(f(n)) ⊂ SPACE(f^2(n))
            だから、違いがある可能性はあるんだよね。
            漸近的解析の曖昧さがこの違いを吸収しているだけで……

            • 「漸近的解析による複雑性クラスがチューリングマシン・回路計算量のモデルと矛盾しているという可能性」ですが、別の可能性として、「漸近的解析による複雑性クラスは曖昧すぎて集合として扱うことができない可能性」というのがあります。
              この場合、複雑性クラスは集合の公理系(ZFなど)で扱えないので、数学の枠組みでは証明不可になりそうですね。

              • by Anonymous Coward

                根本的な理解が間違っている、あるいは間違いを無視しているとしか思えない。
                端的に言ってもわかってもらえないみたいなのでちゃんと書く。

                第三の条件を日本語で書くとこうだな?
                『P問題である判定問題AとBについて、「AまたはB」がP問題でないものが存在する』
                これは false だ、と最初のコメントの非常にシンプルなプログラムが示している。
                だからそもそも証明が成り立っていない。

                P問題を論理和で組み合わせてPにならないものもあるだろうって?
                確かに、無限に組み合わせたら可能性はあるだろう。
                ただ、有限個の組み合わせならばPのままだし、上の命題が示しているのはこの場合

              • どうもお疲れ様です。
                やっぱりここは引っかかりますよね。私も悩みました。

                >『P問題である判定問題AとBについて、「AまたはB」がP問題でないものが存在する』
                >これは false だ、と最初のコメントの非常にシンプルなプログラムが示している。

                上記の証明では、これがTrueであることを、
                ・P問題の論理和と否定がP問題ならば、P問題の論理和と否定の組み合わせで任意の論理式を構成できること。
                ・回路族の回路を論理式と同様に構成することにより、任意の回路族を構成できること。(任意の回路族がこのように構成した回路族の集合に含まれること)
                により示しています。後述も参照して

              • すみません。ちょっと修正です。
                >この有限・無限の嫌らしい問題をP=NPの仮定の中に押し込むために

                仮定は
                「P問題x,y,zの論理和x∨y及び否定¬zが全てPに含まれる」
                ですね。
                P問題zの否定¬zは全てPに含まれる(第二の条件の証明)ので、実質的に
                「P問題x,y,zの論理和x∨yが全てPに含まれる」
                となります。

                親コメント

ナニゲにアレゲなのは、ナニゲなアレゲ -- アレゲ研究家

処理中...