文献

J-GLOBAL ID：201302290451332832   整理番号：13A1425838

計算限界の解明への多面的アプローチ-P vs NPに向けた最前線-2.線形計画法と計算限界

著者 (1件)： 上野賢哉 (京大 白眉セ)
資料名： 電子情報通信学会誌  (Journal of the Institute of Electronics, Information and Communication Engineers)
巻： 96  号： 9  ページ： 675-678  発行年： 2013年09月01日 
JST資料番号： F0019A  ISSN： 0913-5693  資料種別： 逐次刊行物 (A)
記事区分： 解説  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： 多項式時間で計算が可能な問題の集合であるPと多項式時間での計算が不可能であると予想されているNPとの非等価性(P≠NP)を証明するための有力候補の一つとして,論理回路の計算限界が研究されている。NPに属する問題に対して,その問題を表す論理回路を構成するために必要となる素子数を多項式個以内に抑えるような効率的な方法が存在しないことを証明できれば,P≠NPが導けることが知られている。そこで,様々な制限を付けた回路や逆に能力を拡張した回路を利用して,道筋を切り開くための道具を開発しているのが論理回路の計算限界に関する研究動向である。本稿では,このような,計算において可能性と限界の探究は表裏一体であるといった考え方に基づいて,線形計画法の線形緩和・双対定理を利用した計算限界解析法の一例について解説した。線形計画法を利用した下界証明手法は様々な計算限界解析に応用可能な考え方であり,更なる研究の深化が望まれる。

シソーラス用語： *計算理論 ,  *NP困難 ,  *計算量 ,  *限界 ,  賞罰 ,  計算量理論 ,  NP完全問題 ,  アルゴリズム ,  *線形計画法
準シソーラス用語： ゲーデル賞 ,  *計算限界 ,  将来展望 ,  多項式時間アルゴリズム

分類 (1件)： 計算理論  (JB02000A)

タイトルに関連する用語 (5件)： 計算 ,  限界 ,  Vs ,  Np ,  線形計画法