| 講演名 | 2010-07-02 言語認識の複雑さと関数計算の複雑さの関係(セキュリティ関係,一般) 長谷川 真吾, 磯辺 秀司, 静谷 啓樹, |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 本稿では,言語のクラスNPとその証拠を計算する関数のクラスNPMV_gについてその関係性を探索する.クラスNPとクラスNPMV_gは,self-computabilityと呼ばれる性質により様々な研究がなされているが,今回我々はそれをいくらか緩和した条件を考え,次の結果を得た:dom f∈coNPであるf∈NPMV_gに対し,1)f∈FewPF_gならば,fはあるNP∩coNPに属する言語に帰着する;2)任意のf∈NPMV_gについて,fがNP∩coNPに属する言語に帰着するならば,NP=coNP. |
| 抄録(英) | We explore the relationship between the class NP and the function class NPMV_g, the set of witness functions for languages in NP. The relationship between NP and NPMVg is studied in the context of the self-computability of sets. In this paper, we consider slightly relaxed valiant of the self-computability and show the following two results for functions in NPMV_g with coNP domains: 1) for any function f in FewPF_g, f reduces an NP∩coNP language; and 2) any function f in NPMV_g reduces an NP∩coNP language only when NP = coNP. |
| キーワード(和) | 多価関数 / NP / NPMV_g / self-computability |
| キーワード(英) | multivalued function / NP / NPMV_g / self-computability |
| 資料番号 | ISEC2010-37,SITE2010-33,ICSS2010-43 |
| 発行日 |
| 研究会情報 | |
| 研究会 | ICSS |
|---|---|
| 開催期間 | 2010/6/24(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Information and Communication System Security (ICSS) |
|---|---|
| 本文の言語 | ENG |
| タイトル（和） | 言語認識の複雑さと関数計算の複雑さの関係(セキュリティ関係,一般) |
| サブタイトル（和） | |
| タイトル（英） | On the Relationship between Recognizing Languages and Computing Functions |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 多価関数 / multivalued function |
| キーワード(2)（和/英） | NP / NP |
| キーワード(3)（和/英） | NPMV_g / NPMV_g |
| キーワード(4)（和/英） | self-computability / self-computability |
| 第 1 著者 氏名（和/英） | 長谷川 真吾 / Shingo HASEGAWA |
| 第 1 著者 所属（和/英） | 東北大大学院情報科学研究科 Graduate School of Information Sciences, Tohoku University |
| 第 2 著者 氏名（和/英） | 磯辺 秀司 / Shuji ISOBE |
| 第 2 著者 所属（和/英） | 東北大大学院情報科学研究科 Graduate School of Information Sciences, Tohoku University |
| 第 3 著者 氏名（和/英） | 静谷 啓樹 / Hiroki SHIZUYA |
| 第 3 著者 所属（和/英） | 東北大大学院情報科学研究科 Graduate School of Information Sciences, Tohoku University |
| 発表年月日 | 2010-07-02 |
| 資料番号 | ISEC2010-37,SITE2010-33,ICSS2010-43 |
| 巻番号（vol） | vol.110 |
| 号番号（no） | 115 |
| ページ範囲 | pp.- |
| ページ数 | 6 |
| 発行日 | |