言語認識の複雑さと関数計算の複雑さの関係(セキュリティ関係,一般)
スポンサーリンク
概要
- 論文の詳細を見る
本稿では,言語のクラス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.
- 社団法人電子情報通信学会の論文
- 2010-06-24
著者
-
静谷 啓樹
東北大学情報処理教育センター
-
静谷 啓樹
東北大学 大学院情報科学研究科 情報基礎科学専攻
-
磯辺 秀司
東北大学大学院情報科学研究科
-
磯辺 秀司
東北大大学院情報科学研究科
-
長谷川 真吾
東北大学大学院情報科学研究科
-
長谷川 真吾
東北大大学院情報科学研究科
-
静谷 啓樹
東北大大学院情報科学研究科
関連論文
- 代数的トーラス上の離散対数問題に関する計算量理論的考察(情報通信基礎サブソサイエティ合同研究会)
- 暗号文中のキーワードの有無の証明法
- 追跡可能性を有する部分ブラインド署名の一構成(情報通信基礎サブソサイエティ合同研究会)
- 追跡可能性を有する部分ブラインド署名の一構成(情報通信基礎サブソサイエティ合同研究会)
- 追跡可能性を有する部分ブラインド署名の一構成(情報通信基礎サブソサイエティ合同研究会)
- 有向グラフに対する推移署名方式の構成法(ブロードバンドモバイル時代における基礎技術)(情報通信サブソサイエティ合同研究会)
- 有向グラフに対する推移署名方式の構成法(ブロードバンドモバイル時代における基礎技術)(情報通信サブソサイエティ合同研究会)
- 有向グラフに対する推移署名方式の構成法(ブロードバンドモバイル時代における基礎技術)(情報通信サブソサイエティ合同研究会)
- 大学における情報リテラシー教育の最近の動向(2.第1回情報シナジー研究会)
- 素因数分解と離散対数問題アルゴリズム ( 数論アルゴリズムとその応用)