講演抄録/キーワード |
講演名 |
2011-03-04 14:55
多価関数における自己帰着とmany-one型帰着について ○許 智元・磯辺秀司・小泉英介・静谷啓樹(東北大) IT2010-127 ISEC2010-131 WBS2010-106 |
抄録 |
(和) |
本稿では, 多価関数のクラスにおける自己帰着とmany-one型帰着の関係について考察する. 結果として, parsimonious (many-one または metric many-one)帰着に関するすべてのNPMV (またはNPMVg) 完全関数がTuring length-decreasing self-reducibleならば, NPMV (または NPMVg) に属するすべての関数に対して, 多項式時間計算可能な洗練が存在することを示した. このことは, P $\neq$ NP である限り, NPMV (または NPMVg) 完全かつTuring length-decreasing self-reducibleでない関数が存在することを意味している. |
(英) |
In this paper, we investigate a relationship between the self-reducibility and the many-one-like reducibilities for multi-valued functions. We show that if any parsimonious (many-one or metric many-one) complete function for NPMV (or NPMVg) is Turing length-decreasing self-reducible, then any function in NPMV (or NPMVg) has a refinement that is polynomial-time computable. This result means that there exists an NPMV (or NPMVg)-complete function that is not Turing length-decreasing self-reducible unless P=NP. |
キーワード |
(和) |
多価関数 / Turing length-decreasing self-reduction / many-one型帰着 / / / / / |
(英) |
multi-valued function / Turing length-decreasing self-reduction / many-one-like reduction / / / / / |
文献情報 |
信学技報, vol. 110, no. 443, ISEC2010-131, pp. 389-394, 2011年3月. |
資料番号 |
ISEC2010-131 |
発行日 |
2011-02-24 (IT, ISEC, WBS) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
IT2010-127 ISEC2010-131 WBS2010-106 |
|