| 講演名 | 2014-09-02 The World of Combinatorial Fuzzy Problems and the Efficiency of Fuzzy Approximation Algorithms : Preliminary Report , |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | |
| 抄録(英) | 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 Puzzy-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 |
| 資料番号 | COMP2014-20 |
| 発行日 |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 2014/8/26(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Theoretical Foundations of Computing (COMP) |
|---|---|
| 本文の言語 | ENG |
| タイトル（和） | |
| サブタイトル（和） | |
| タイトル（英） | The World of Combinatorial Fuzzy Problems and the Efficiency of Fuzzy Approximation Algorithms : Preliminary Report |
| サブタイトル（和） | |
| キーワード(1)（和/英） | / combinatorial fuzzy problem |
| 第 1 著者 氏名（和/英） | / Tomoyuki YAMAKAMI |
| 第 1 著者 所属（和/英） | Department of Information Science, University of Fukui |
| 発表年月日 | 2014-09-02 |
| 資料番号 | COMP2014-20 |
| 巻番号（vol） | vol.114 |
| 号番号（no） | 199 |
| ページ範囲 | pp.- |
| ページ数 | 8 |
| 発行日 | |