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

【ご意見募集】P≠PHの証明(P≠NPの証明)」記事へのコメント

  • おっしゃりたいことは
    NTD を導入すると P ⊂ NTD ⊆ PH となる,だから P != PH ってことですか?

    でもそれは NTD を導入したからであって
    NTD以外のアルゴリズム,つまり理想的な アルゴリズム X が見つかれば
    P = X = PH
    となりませんか?

    証明すべきはそのような X が存在しないことでは無いでしょうか?
    多くの人はそのようなXは存在しないと信じてますが,
    存在しないことを証明するのが P != NP のキモだと思います.

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

      > NTD を導入すると P ⊂ NTD ⊆ PH となる,だから P != PH ってことですか?

      いいえ。問題のクラスで表すと
      PH ∋ NTD ∉ P
      --> P != PH
      ですね。

      定義1(とSipserの証明)より
      P ⊂ 入力長の多項式規模のNNF回路族で計算できる問題のクラス

      定理13より
      NTD ∉ 入力長の多項式規模のNNF回路族で計算できる問題のクラス

      定理10より
      NTD ∈ PH

      から、定理14にて
      ・定義1、定理13より
       NTD ∉ P
      ・定理10より
       NTD ∈ PH
      よって
      PH ∋ NTD ∉ P
      --> P != PH
      を導いています。

      • たとえば
        NTD ∉ P

        x(NTD) ∈ P
        と変換する x() が存在するとどうなるでしょうか?

        個人的には,そんなx()は存在しないと思いますが,
        その存在を議論することが自体が P!=NP の問だと思います

        • そのようなxは存在しますが、多項式時間還元にはなりません。

          多項式時間還元でx(NTD) ∈ Pとなるxが存在する
          -->(x(NTD) ∈ Pより)入力長の多項式規模のNNF回路族でx(NTD)が計算できる。
          -->(xが多項式時間還元となることより)入力長の多項式規模のNNF回路族でNTDが計算できる。
          となり、定理13と矛盾します。

          • by Anonymous Coward

            「定理13と矛盾する」とおっしゃっていますが
            それは「NTDを計算するNNF回路族の素子数は多項式規模に収まらない。」と決め込んでいるからではありませんか?
            これは正しくは「今の所,多項式規模還元する方法が見つかっていないだけ」だと思います.

            • by fiercewinds (22740) on 2018年03月14日 22時35分 (#3376476) 日記

              この部分が本証明の肝となります。

              定理3より、
              NNF回路族には(隣の入力のペアの)差分部分のどちらか片方を含む時のみに1になるAND素子が存在。
              −>隣の入力のペア毎に1つ以上のAND素子が必要。(さもなければ間の入力を区別できない)

              定理12(及び定理5、8、9、11)より、
              NTDに含まれる隣の入力のペアの濃度は、入力長に対して多項式規模に収まらない。

              よって、NTDを計算するNNF回路族の素子数は多項式規模に収まりません。

              親コメント
              • by Anonymous Coward

                肝というか,DTMをエミュレートしているので自明だと思うのですが…

              • by fiercewinds (22740) on 2018年03月15日 8時36分 (#3376652) 日記

                肝というのは、
                「隣の入力のペア毎に1つ以上のAND素子が必要」
                「NTDに含まれる隣の入力のペアの濃度は、入力長に対して多項式規模に収まらない」
                −>「NTDを計算するNNF回路族の(AND)素子数は多項式規模に収まらない」
                の部分です。

                上記は、DTMをエミュレートしているからと言って自明ではありません。

                親コメント
              • ああいうと、実はこれで。
                こういうと、これはあれで。

              • by Anonymous Coward

                >「隣の入力のペア毎に1つ以上のAND素子が必要」
                「毎に」というのはなぜ?
                その素子は他の入力では反応しないことが証明されるの?

一つのことを行い、またそれをうまくやるプログラムを書け -- Malcolm Douglas McIlroy

処理中...