非数値的な極値問題の計算量に関する研究

点击翻译按钮获取中文摘要

近年の計算量理論において,離散的な対象に関してある種の性質を満たす極大な部分や極小な部分を計算することを目的とした計算問題の研究が盛んに行われている(以下このような問題を極値問題と呼ぶ).例えば,無向グラフの極大独立点集合を求める問題やブール式の極大充足割当を求める問題などがその代表例である.これまでの全ての研究は,個々の問題に対して効率的なアルゴリズムを設計するかもしくはその計算量を決定することに注がれてきており,より一般的な枠組みに基づいた研究は行われていなかった.そこで本研究では,極値問題の計算量を決定するための一般的な枠組みを用意し,各極値問題が効率よく計算できるための条件および計算困難となる条件を明かにすることを目的として研究を進めた.極値問題の計算量を分析するに当たって,極値問題の基本構造を定める入力-解関係の計算量と各入力に関する解空間の構造的な性質である遺伝性に着目し,次に述べる結果を得た.1.入力-解関係が多項式時間判定可能でかつ解空間が遺伝的であるときには,極値問題を多項式時間で計算できる.2.入力-解関係が多項式時間判定可能もしくはNP-判定可能でかつ解空間が非遺伝的であるときには,極値問題の計算量はFP^<NP>_||-完全問題と等価である.3.入力-解関係がNP-判定可能でかつ解空間が遺伝的であるときにも,極値問題の計算量はFP^<NP>_||-完全問題と等価である.4.入力-解関係がcoNP-判定可能でかつ解空間が遺伝的であるときには,極値問題の計算量はFP^<NP>_||-完全問題より困難であるが,FP^<NP>_||-完全問題よりは低い.5.入力-解関係がcoNP-判定可能でかつ解空間が非遺伝的であるときには,極値問題の計算量はFPSIGMA^p_2||-完全問題と等価である.入力-解関係が多項式時間判定可能でかつ解空間が遺伝的である場合,ならびに,入力-解関係がcoNP-判定可能でかつ解空間が遺伝的である場合について詳細な分析を試みたが十分な結果が得られず,今後の研究課題として残している.尚,上記の結果は論文誌に投稿中であり,すでに第一回目の審査・校正を完了している.