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

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

  • by Anonymous Coward on 2014年09月09日 15時02分 (#2673528)

    >∀p,q∈P(p∨q∈NP)
    これの意味がわかりません。特に、p∨qのところ。

    2つの問題p, qがあったとして、その論理和ってどんな問題なんですか?

    • by fiercewinds (22740) on 2014年09月09日 22時33分 (#2673822) 日記

      まずp∨qですが、
      任意の入力xに対してp(x)=u、q(x)=vとなる時、
      (p∨q)(x)=u∨v
      となる合成問題(関数)がp∨qとなります。

      問題pかあるいは問題qがどちらかの出力が真になるとき、その時に限り真になる問題がp∨qです。

      問題p,qに対応する論理式とその論理和(正確には入力長ごとに異なる論理式の集合)をイメージするといいと思います。

      次に∀p,q∈P(p∨q∈NP)を説明します。
      これは言葉で書くと「Pに属する全ての問題p,qの論理和p∨qはNPに属する」という命題を表しています。p,qがPに属するとき、必ず上記のp∨qはNPに属することを主張しています。

      非決定性チューリングマシンをご存知でしたら、最初に問題pを解く決定性チューリングマシンと問題qを解く決定性チューリングマシンに(選択的に)分岐する非決定性チューリングマシンをイメージするといいかと思います。

      親コメント

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

処理中...