| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2014-09-02 14:45 The World of Combinatorial Fuzzy Problems and the Efficiency of Fuzzy Approximation Algorithms -- Preliminary Report -- ○Tomoyuki Yamakami（Univ. of Fukui）  COMP2014-20 |
|
| 抄録 | （和） | (まだ登録されていません) |
| （英） | We re-examine a practical aspect of combinatorial fuzzy problems of various types, including search, counting, optimization, and decision problems. We are focused only on those fuzzy problems that take series of fuzzy input objects and output fuzzy values. To solve such problems efficiently, we design efficient fuzzy algorithms, which are modeled by polynomial-time deterministic fuzzy Turing machines equipped with read-only auxiliary tapes and write-only output tapes and also by polynomial-size fuzzy circuits composed of fuzzy gates. We also introduce fuzzy proof verification systems to model the fuzzification of nondeterminism. Those models help us identify four complexity classes: Fuzzy-FPA of fuzzy functions, Fuzzy-PA and Fuzzy-NPA of fuzzy decision problems, and Fuzzy-NPAO of fuzzy optimization problems. Based on a relative approximation scheme of fuzzy membership degree, we formulate two notions of "reducibility" in order to compare the computational complexity of two fuzzy problems. These reducibility notions make it possible to locate the most difficult fuzzy problems in Fuzzy-NPA and in Fuzzy-NPAO. |
|
| キーワード | （和） | / / / / / / / |
| （英） | combinatorial fuzzy problem / fuzzy Turing machine / fuzzy circuit / reducibility / complete problem / / / | |
| 文献情報 | 信学技報, vol. 114, no. 199, COMP2014-20, pp. 35-42, 2014年9月. | |
| 資料番号 | COMP2014-20 | |
| 発行日 | 2014-08-26 (COMP) | |
| ISSN | Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | COMP2014-20 |
|
| 研究会情報 | |
| 研究会 | COMP |
| 開催期間 | 2014-09-02 - 2014-09-02 |
| 開催地（和） | 豊橋技術科学大学 |
| 開催地（英） | Toyohashi University of Technology |
| テーマ（和） | |
| テーマ（英） | |
| 講演論文情報の詳細 | |
| 申込み研究会 | COMP |
| 会議コード | 2014-09-COMP |
| 本文の言語 | 英語 |
| タイトル（和） | |
| サブタイトル（和） | |
| タイトル（英） | The World of Combinatorial Fuzzy Problems and the Efficiency of Fuzzy Approximation Algorithms |
| サブタイトル（英） | Preliminary Report |
| キーワード(1)（和/英） | / combinatorial fuzzy problem |
| キーワード(2)（和/英） | / fuzzy Turing machine |
| キーワード(3)（和/英） | / fuzzy circuit |
| キーワード(4)（和/英） | / reducibility |
| キーワード(5)（和/英） | / complete problem |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | Tomoyuki Yamakami / Tomoyuki Yamakami / |
| 第1著者 所属（和/英） | 福井大学 (略称： 福井大) University of Fukui (略称： Univ. of Fukui) |
| 講演者 | 第1著者 |
| 発表日時 | 2014-09-02 14:45:00 |
| 発表時間 | 30分 |
| 申込先研究会 | COMP |
| 資料番号 | COMP2014-20 |
| 巻番号（vol） | vol.114 |
| 号番号（no） | no.199 |
| ページ範囲 | pp.35-42 |
| ページ数 | 8 |
| 発行日 | 2014-08-26 (COMP) |
[研究会発表申込システムのトップページに戻る]