アカウント名:
パスワード:
>∀p,q∈P(p∨q∈NP)これの意味がわかりません。特に、p∨qのところ。
2つの問題p, qがあったとして、その論理和ってどんな問題なんですか?
まず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を解く決定性チューリングマシンに(選択的に)分岐する非決定性チューリングマシンをイメージするといいかと思います。
より多くのコメントがこの議論にあるかもしれませんが、JavaScriptが有効ではない環境を使用している場合、クラシックなコメントシステム(D1)に設定を変更する必要があります。
あと、僕は馬鹿なことをするのは嫌いですよ (わざとやるとき以外は)。-- Larry Wall
定義が? (スコア:0)
>∀p,q∈P(p∨q∈NP)
これの意味がわかりません。特に、p∨qのところ。
2つの問題p, qがあったとして、その論理和ってどんな問題なんですか?
Re:定義が? (スコア:1)
まず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を解く決定性チューリングマシンに(選択的に)分岐する非決定性チューリングマシンをイメージするといいかと思います。