| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2013-06-24 13:20 ［チュートリアル講演］計算複雑さへの招待（3）：数理計画法から攻める計算限界 ○上野賢哉（京大）  COMP2013-22 |
|
| 抄録 | （和） | 本発表は，新学術領域（計算限界解明）プロジェクトのチュートリアルシリーズの第三弾目である．今回のチュートリアルでは，数理計画法の視点から見た計算限界に焦点を当て，最新の研究動向を概説する．前回のチュートリアルは，P≠NPに対してNPの側を大きくするような接近法であったが，今回はPの側を小さくすることによりP≠NPへと接近する方向性を取り上げることになる．特に，1991年にYannakakisによって確立された理論を基盤として，2012年にFiorini，Massar，Pokutta，Tiwary，de Wolfにより証明された，NP完全問題を表現する線形計画法の複雑さに対する超多項式下界について説明する． |
| （英） | This presentation corresponds to the third tutorial of the ELC (Exploring the Limits of Computation) project supported by Grant-in-Aid for Scientific Research on Innovative Areas. In this tutorial, we focus on the limitations of computation from the viewpoint of mathematical programming and overview recent research achievements. We pick up approaches to P ≠ NP by weakening P, while we studied approaches to P ≠ NP by enhancing NP in the previous tutorial. In particular, we explain super-polynomial lower bounds on the complexity of linear programming expressing some NP-complete problems proven by Fiorini, Massar, Pokutta, Tiwary, de Wolf in 2012 based on the theory established by Yannakakis in 1991. | |
| キーワード | （和） | 計算限界 / 計算複雑さの理論 / 線形計画法 / / / / / |
| （英） | Limitations of Computation / Computational Complexity Theory / Linear Programming / / / / / | |
| 文献情報 | 信学技報, vol. 113, no. 108, COMP2013-22, pp. 21-21, 2013年6月. | |
| 資料番号 | COMP2013-22 | |
| 発行日 | 2013-06-17 (COMP) | |
| ISSN | Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | COMP2013-22 |
|
| 研究会情報 | |
| 研究会 | COMP |
| 開催期間 | 2013-06-24 - 2013-06-24 |
| 開催地（和） | 奈良女子大学 |
| 開催地（英） | Nara Women's University |
| テーマ（和） | |
| テーマ（英） | |
| 講演論文情報の詳細 | |
| 申込み研究会 | COMP |
| 会議コード | 2013-06-COMP |
| 本文の言語 | 日本語 |
| タイトル（和） | 計算複雑さへの招待（3）：数理計画法から攻める計算限界 |
| サブタイトル（和） | |
| タイトル（英） | Introduction to Computational Complexity Theory (3): Mathematical Programming Approaches to the Limitations of Computation |
| サブタイトル（英） | |
| キーワード(1)（和/英） | 計算限界 / Limitations of Computation |
| キーワード(2)（和/英） | 計算複雑さの理論 / Computational Complexity Theory |
| キーワード(3)（和/英） | 線形計画法 / Linear Programming |
| キーワード(4)（和/英） | / |
| キーワード(5)（和/英） | / |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 上野 賢哉 / Kenya Ueno / ウエノ ケンヤ |
| 第1著者 所属（和/英） | 京都大学 (略称： 京大) Kyoto University (略称： Kyoto Univ.) |
| 第2著者 氏名（和/英/ヨミ） | / / |
| 第2著者 所属（和/英） | (略称： ) (略称： ) |
| 第3著者 氏名（和/英/ヨミ） | / / |
| 第3著者 所属（和/英） | (略称： ) (略称： ) |
| 第4著者 氏名（和/英/ヨミ） | / / |
| 第4著者 所属（和/英） | (略称： ) (略称： ) |
| 第5著者 氏名（和/英/ヨミ） | / / |
| 第5著者 所属（和/英） | (略称： ) (略称： ) |
| 第6著者 氏名（和/英/ヨミ） | / / |
| 第6著者 所属（和/英） | (略称： ) (略称： ) |
| 第7著者 氏名（和/英/ヨミ） | / / |
| 第7著者 所属（和/英） | (略称： ) (略称： ) |
| 第8著者 氏名（和/英/ヨミ） | / / |
| 第8著者 所属（和/英） | (略称： ) (略称： ) |
| 第9著者 氏名（和/英/ヨミ） | / / |
| 第9著者 所属（和/英） | (略称： ) (略称： ) |
| 第10著者 氏名（和/英/ヨミ） | / / |
| 第10著者 所属（和/英） | (略称： ) (略称： ) |
| 第11著者 氏名（和/英/ヨミ） | / / |
| 第11著者 所属（和/英） | (略称： ) (略称： ) |
| 第12著者 氏名（和/英/ヨミ） | / / |
| 第12著者 所属（和/英） | (略称： ) (略称： ) |
| 第13著者 氏名（和/英/ヨミ） | / / |
| 第13著者 所属（和/英） | (略称： ) (略称： ) |
| 第14著者 氏名（和/英/ヨミ） | / / |
| 第14著者 所属（和/英） | (略称： ) (略称： ) |
| 第15著者 氏名（和/英/ヨミ） | / / |
| 第15著者 所属（和/英） | (略称： ) (略称： ) |
| 第16著者 氏名（和/英/ヨミ） | / / |
| 第16著者 所属（和/英） | (略称： ) (略称： ) |
| 第17著者 氏名（和/英/ヨミ） | / / |
| 第17著者 所属（和/英） | (略称： ) (略称： ) |
| 第18著者 氏名（和/英/ヨミ） | / / |
| 第18著者 所属（和/英） | (略称： ) (略称： ) |
| 講演者 | 第1著者 |
| 発表日時 | 2013-06-24 13:20:00 |
| 発表時間 | 90分 |
| 申込先研究会 | COMP |
| 資料番号 | COMP2013-22 |
| 巻番号（vol） | vol.113 |
| 号番号（no） | no.108 |
| ページ範囲 | p.21 |
| ページ数 | 1 |
| 発行日 | 2013-06-17 (COMP) |
[研究会発表申込システムのトップページに戻る]