| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2016-10-21 14:30 フロベニウス問題の計算複雑さの下界とその部分問題 ○松原俊一（青学大）  COMP2016-28 |
|
| 抄録 | （和） | 本稿ではフロベニウスの問題の計算複雑さの下界について考える．フロベニウスの問題は，与えられた $n$ 個の互いに素な正整数 $a_1,cdots,a_n$について，その非負整数結合 $sum_{i=1}^n c_i a_i$ として表すことのできない最大数を求める問題である．この問題は計算困難な問題であることが知られているが，高速なアルゴリズムの実装もさかんに行われている．しかしながら計算複雑さの下界についての研究の試みは知られていない．本研究ではフロベニウスの問題の計算複雑さの下界について，フロベニウス循環グラフによりある性質を示す． |
| （英） | In this paper, we lower bounds for the time complexity of the Frobenius problem. Given a set $A$ of coprime positive integers,we call an integer $g(A)$ the {itshape Frobenius number} if $g(A)$ is the maximum among integers that cannot be represented as nonnegative integer combinations of $A$. We call the problem of finding $g(A)$ for a given set $A$ of coprime positive integers the {itshape Frobenius problem}. A lot of fast practical algorithms were developed while this problem is known to be computationally hard. However, the results on lower bounds for its time complexity have never been known. We initiate to investigate lower bounds for the time complexity of the Frobenius problem. | |
| キーワード | （和） | フロベニウス / フロベニウス数 / 計算複雑さ / 計算下界 / 最短経路問題 / / / |
| （英） | Frobenius problem / Frobenius number / computational complexity / lower bound for the time complexity / shortest path problem / / / | |
| 文献情報 | 信学技報, vol. 116, no. 262, COMP2016-28, pp. 35-37, 2016年10月. | |
| 資料番号 | COMP2016-28 | |
| 発行日 | 2016-10-14 (COMP) | |
| ISSN | Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | COMP2016-28 |
|
| 研究会情報 | |
| 研究会 | COMP |
| 開催期間 | 2016-10-21 - 2016-10-21 |
| 開催地（和） | 東北大学 |
| 開催地（英） | Tohoku University |
| テーマ（和） | |
| テーマ（英） | |
| 講演論文情報の詳細 | |
| 申込み研究会 | COMP |
| 会議コード | 2016-10-COMP |
| 本文の言語 | 英語（日本語タイトルあり） |
| タイトル（和） | フロベニウス問題の計算複雑さの下界とその部分問題 |
| サブタイトル（和） | |
| タイトル（英） | On lower bounds for the complexity of the Frobenius problem and its subproblems |
| サブタイトル（英） | |
| キーワード(1)（和/英） | フロベニウス / Frobenius problem |
| キーワード(2)（和/英） | フロベニウス数 / Frobenius number |
| キーワード(3)（和/英） | 計算複雑さ / computational complexity |
| キーワード(4)（和/英） | 計算下界 / lower bound for the time complexity |
| キーワード(5)（和/英） | 最短経路問題 / shortest path problem |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 松原 俊一 / Shunichi Matsubara / マツバラ シュンイチ |
| 第1著者 所属（和/英） | 青山学院大学 (略称： 青学大) Aoyama Gakuin University (略称： Aoyama Gakuin 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著者 |
| 発表日時 | 2016-10-21 14:30:00 |
| 発表時間 | 30分 |
| 申込先研究会 | COMP |
| 資料番号 | COMP2016-28 |
| 巻番号（vol） | vol.116 |
| 号番号（no） | no.262 |
| ページ範囲 | pp.35-37 |
| ページ数 | 3 |
| 発行日 | 2016-10-14 (COMP) |
[研究会発表申込システムのトップページに戻る]