最適解を求める複雑さについて

• Item type: SIG Technical Reports(1)
• 公開日: 1990-11-22
• タイトル: 最適解を求める複雑さについて
• タイトル / 言語: en
• タイトル: ON THE COMPLEXITY OF COMPUTING OPTIMAL SOLUTIONS
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 電気通信大学情報工学科
• 著者所属: 電気通信大学情報工学科
• 著者所属(英): en
• 著者所属(英): Department of Computer Science and Information Mathematics University of Electro - Communications
• 著者所属(英): en
• 著者所属(英): Department of Computer Science and Information Mathematics University of Electro-Communications
• 著者名: 陳致中; 戸田, 誠之助
• 著者名(英): Zhi-Zhong, Chen; Seinosuke, Toda
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 解の値が入力の長さの多項式で抑えられるNP最適化問題(C)に対し，最適解を求める計算量について述べる。任意のNPCOP IIに対して，IIの実例を入力として与えられたら，NPオラックルヘ一組のパラレル質問をし，その答えを評価して一つの最適解を非常に高い確率で出力する確率アルゴリズムが存在することを示す。更に，幾つかの自然なNPCOP'sに対し，最適解を計算するどの関数もPF^<NP>_<tt>にある関数と少なくとも同じ難しさを持つことを示す。
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: We study the complexity of computing optimal solutions for NP optimization problems whose solution costs are bounded above by a polynomial in the length of their instances (we call such an NP optimization problem an NPCOP). We first show that for any NPCOP II, there exists a polynomial-time bounded randomized algorithm which, given an instance of II, uses one free evaluation of parallel queries to an NP oracle set and outputs some optimal solution with very high probability. We then show that for several natural NPCOP's, any function giving those optimal solutions is at least as hard as all functions in PF^<NP>_<tt>.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 情報処理学会研究報告アルゴリズム（AL）; 巻 1990, 号 94(1990-AL-018), p. 1-8, 発行日 1990-11-22
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会