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

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

  • たとえば
    > NTDの濃度は多項式規模に収まらない。よって、NTDを計算するNNF回路族の素子数は多項式規模に収まらない。
    ここの「よって、」は P≠NPを仮定してませんか?

    • ご指摘ありがとうございます。
      ここはちょっと修正&補足が必要そうです。

      まず「NTDの濃度は多項式規模に収まらない」の部分ですが、正確には
      「NTDにある隣の入力のペアの濃度は多項式規模に収まらない」
      ですね。定理12もそれに合わせて
      定理12
      NTDに含まれる隣の入力のペアの濃度は、入力長に対して多項式規模に収まらない。
      に修正した方が良さそうですね……

      また、「よって」の部分ですが、
      定理3:
      NNF回路には、入力が少なくとも(対応する)差分部分のどちらか片方を
      含む時のみに1になるAND素子が存在する。
      −>NTDのそれぞれの隣の入力毎に、(受理すべき隣の入力の差分部分全体と
        拒否すべき間の入力を判別するために)入力がその差分部分全体を含むかどうかを
        判定する独自のAND素子を持つ必要がある。

      を前提とする「よって」になります。
      定理3自体はP≠NPを仮定していませんので、この「よって」もP≠NPを
      仮定していません。

      後で説明の補強を考えることにします。
      #単純に「定理3より」のような説明を追加する感じですかね。

      親コメント

犯人は巨人ファンでA型で眼鏡をかけている -- あるハッカー

処理中...