多項式時間変換

質問

初めまして。多項式時間還元について質問させて下さい。
問題Aが問題Bに多項式時間還元できるかの証明として

(1)問題Aの任意の問題例xを多項式時間で問題Bの問題例に変換しているか.
yes:解がある. no:解がない.として
(2)問題Bがyes(no)ならば問題Aもyes(no).
(3)問題Aがyes(no)ならば問題Bもyes(no).

この(1)(2)(解の一致)と(3)(多項式時間で還元か)が必要だと思います.

また,「還元できるならBはAと同程度に言える」とされています.
ここで２つ質問があるのですが
１つめはAがno(解がない)ならBもno,BがnoならAもnoの証明
から多項式還元可能が言えたとして「Bが解けないなら,Aも解けてない」なら問題の難しさ
比較ができなくて,同程度に難しいが言えないと思うのですがどうなのでしょうか.

２つめは,証明(2)(3)の事で.「Bが解ければAは自動で解ける.」と還元の性質より
証明(2)で矛盾を確かめているのはわかります.
しかし(3)の方は何を確かめたくてしているのかわからないので教えてください.

回答No.2

Tacosan · ベストアンサー

あ, すみません, 間違えました. この内容は「多項式時間変換」に限定したものです. 「多項式時間還元」で一般的に成り立つものではありません.
既に書いたように, 「A から B に多項式時間還元できる」というのは「B を解くオラクルがあれば A を多項式時間で解くことができる」ということです. B を解くオラクルを使うためには, 与えられた A の問題例から B の問題例を (多項式時間で) 作る必要がありますが, B の問題例を「1個だけ」作るとは限りませんし, 与えられた A の問題例の答え (yes/no) が作られた B の問題例の答え (yes/no) と一致する必要もありません.
極端にいえば, 問題 A とその補問題 A' (A の yes/no を反転した問題) があれば, 「A から A' に多項式時間還元できる」ことになります. つまり, A の問題例 x が与えられたときに, A' を解くオラクルに x を与えます. すると yes/no が得られるわけですが, これは A の問題例としての yes/no とはちょうど正反対です. つまり, 「A' を解くオラクルに x を与えて得られる答え」の yes/no を反転すればよく, これは「A' を解くオラクルを用いた A の多項式時間アルゴリズム」です.
まあ, 普通「A が B に還元できる」ということを示すときには「A から B への変換」を作る (つまり「A から B に変換できる」から「還元可能」ということを示す) んですけど, 一般論として「常に変換が作れる」とは限りません.
ちなみに「多項式時間還元」と「多項式時間変換」を同じ意味で使うときには, どちらも「多項式時間還元」の意味で使うんじゃないかなぁ.

お礼

なんとなくわかりました。つまり多項式時間還元で
解の一致が求められるのは、変換と還元を同じ意味で使っていたからなんですね。別々の意味だと還元はAの補問題A'にも還元できるし、解が一致する必要もない。またBの問題例を複数個作る事も可能なのですね。
色々有難うございました。アドバイス助かりました。

回答No.3

Tacosan

う～ん, 日本語下手だな～＞自分
#2 の最初の部分は, 「この質問で挙げられている内容が多項式時間変換のものである」という意味です. 意味不明な日本語になっていますが, そんな感じで理解してください.

回答No.1

Tacosan

とりあえず明らかにしておきたいことがあります:
１．「還元」と「変換」が混在しているんですけど, 区別しているんでしょうか? 内容を見る限り区別しないと変な感じはするんですが, 区別していると仮定すると内容がおかしいです. 区別するなら
・A から B に多項式時間還元可能: B を解くオラクルがあれば A は多項式時間で解ける
・A から B に多項式時間変換可能: A の問題例が与えられれば, それと yes/no が一致する B の問題例を多項式時間で生成できる
という意味です.
２．yes/no を「解のある/なし」としていますが, これは間違っています. そもそも「与えられた問題例に対して yes/no を答える」という問題ですから, 解はあるに決まっています. その解が yes (問題によって定まる性質を満たす) か no (性質を満たさない) かのどちらかである, ということです.
で, 2つ目の問題は「還元」と「変換」を区別していないと意味を持たないんですが, 区別しているなら「普通はなくてもいい」ということになりそう. 「変換」の定義から
A の答えが yes iff B の答えが yes
なので, (2) と (3) は (yes/no のどちらかに必ず定まるという前提のもとで) 等価です.
あと, 1つ目の方は「普通そんな表現はしない」というのが正解かな. 普通は
「A から B に多項式時間還元可能 → B は A と同等以上に難しい」
ですね. 「同等に難しい」ことまでは保証しません. これは「変換」でも同じかな.

補足

紛らわしく還元と変換を混同させて申し訳ないのです。
多項式時間変換と多項式時間還元は同じ意味だと解釈してました。
知りたいのは多項式時間還元の方です。

yes,noの意味は、性質を満たすかどうかで解の有る無しではないのですね。言われてみればそう思います。
それで、アドバイスから察すると例えば問題Bがnoならば,問題Bは'解けて'
性質を満たさないことがわかった。なのでAは多項式時間変換+Bのアルゴリズムを使っているのでAも性質を満たさないことがわかる。
つまり「BがnoならAもno」の時でもBは解いているのでAも解けるということなんですね。

最後に、変換の方は証明(3)は「普段はなくてもいい」の意味などは
わかりました。それで、還元の方はやはり証明(3)問題Aがyes(no)ならば問題Bもyes(no)の必要性がわかりません。Bが解ければAも解ける事がいえればいいので(1)(2)だけでいいと思うのですが。