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

NP≠coNPの証明」記事へのコメント

  • by Anonymous Coward

    2.9の証明の始め、Corollary 2.5を使うところで説明が飛んでないか?
    |coPp|=|Pq| や n∈O(m) はどっから来た。
    n∈O(m)は、n∈O(m^k)(kはrの次数)とかの間違い?

    • by fiercewinds (22740) on 2015年12月11日 0時23分 (#2932763) 日記

      ご指摘のとおり、ここはちょっと間違っていて
      |coPp|≦|Pq|
      n∈O(m^k)
      ですね。
      この関係は
      coPp->Pq
      の多項式時間単射還元から来ています。
      この単射が存在するのならば、coPpに対応するPqは高々多項式規模の長さしか違わないので、
      n∈O(m^k)

      |coPp|≦|Pq|
      となるものが存在します。

      親コメント
      • by Anonymous Coward

        v4のTheorem 2.9の証明がおかしい
        |Pb|≦O((L+c)^k)はTheorem 2.8から導いたんだろうけど、
        PbがTheorem 2.8を満たすとは限らない。

        PaとPbを選ぶと、それに応じて単射rが存在し、
        またrに応じて、n∈O(L^k)を定めることができ、
        そのnに応じて、あるP∈ANTI_nが存在し、Theorem 2.8を満たす。
        つまり、最初のPbの選び方によって、Pが変動しうるため、
        PbがPになるように、最初にうまくPbを選べる保証がない

        • by fiercewinds (22740) on 2015年12月12日 17時26分 (#2933759) 日記

          なるほど、確かに確定できないですね……
          Theorem 2.6. を構成するときに気付かずに明示していない条件が入っているようですね。
          問題の複雑性も落ちているかも。

          ちょっと考えてみます。

          親コメント

開いた括弧は必ず閉じる -- あるプログラマー

処理中...