言語認識の複雑さと関数計算の複雑さの関係(セキュリティ関係,一般)
スポンサーリンク
概要
- 論文の詳細を見る
本稿では,言語のクラス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回情報シナジー研究会)
- 素因数分解と離散対数問題アルゴリズム ( 数論アルゴリズムとその応用)
- 多重M系列を用いた通信イミュニティテスト用ランダムパルス列(RPS)発生器の統計検定
- 有限体の離散対数領域上の一般逆行列に基づく公開鍵暗号方式
- 抽象的DDoS攻撃問題の複雑さについて(情報通信基礎サブソサイエティ合同研究会)
- 代数的トーラス上の離散対数問題に関する計算量理論的考察(情報通信基礎サブソサイエティ合同研究会)
- 代数的トーラス上の離散対数問題に関する計算量理論的考察(情報通信基礎サブソサイエティ合同研究会)
- 平成20年度東北大学学士課程入学者の基礎的な情報対応能力について
- 平成20年度東北大学学士課程入学者の基礎的な情報対応能力について
- 平成19年度東北大学学士課程入学者の基礎的な情報対応能力について
- 音情報に対する電子透かし : 乱択法とうなり法(情報通信基礎サブソサイエティ合同研究会)
- 公開鍵基盤の頑健化について(情報通信基礎サブソサイエティ合同研究会)
- 音情報に対する電子透かし : 乱択法とうなり法(情報通信基礎サブソサイエティ合同研究会)
- 公開鍵基盤の頑健化について(情報通信基礎サブソサイエティ合同研究会)
- 音情報に対する電子透かし : 乱択法とうなり法(情報通信基礎サブソサイエティ合同研究会)
- 公開鍵基盤の頑健化について(情報通信基礎サブソサイエティ合同研究会)
- 抽象的DDoS攻撃問題の複雑さについて(情報通信基礎サブソサイエティ合同研究会)
- DH問題とその派生問題の複雑さについて(情報通信基礎サブソサイエティ合同研究会)
- 抽象的DDoS攻撃問題の複雑さについて(情報通信基礎サブソサイエティ合同研究会)
- DH問題とその派生問題の複雑さについて(情報通信基礎サブソサイエティ合同研究会)
- DH問題とその派生問題の複雑さについて(情報通信基礎サブソサイエティ合同研究会)
- 情報教育用計算機システムとその運用状況について(2.第1回情報シナジー研究会)
- グラフ同型を用いた離散対数型暗号の考察
- 無方向性関数について
- 平成19年度東北大学学士課程入学者の基礎的な情報対応能力について
- 東北大学川内北キャンパスの無線ＬＡＮ接続サービス
- IT の教育利用に関する学士課程入学者に対するアンケート調査 ―IT 志向と教育利用ニーズを中心として―
- 平成18 年度東北大学学士課程入学者の基礎的情報対応能力について
- 言語認識の複雑さと関数計算の複雑さの関係(セキュリティ関係,一般)
- 言語認識の複雑さと関数計算の複雑さの関係(セキュリティ関係,一般)
- 言語認識の複雑さと関数計算の複雑さの関係(セキュリティ関係,一般)
- 正則な格子における最近傍格子点問題の複雑さについて(情報通信基礎サブソサイエティ合同研究会)
- 正則な格子における最近傍格子点問題の複雑さについて(情報通信基礎サブソサイエティ合同研究会)
- 正則な格子における最近傍格子点問題の複雑さについて(情報通信基礎サブソサイエティ合同研究会)
- 多価関数における自己帰着とmany-one型帰着について(情報通信基礎サブソサイエティ合同研究会)
- 多価関数における自己帰着とmany-one型帰着について(情報通信基礎サブソサイエティ合同研究会)
- 多価関数における自己帰着とmany-one型帰着について(情報通信基礎サブソサイエティ合同研究会)
- The Computational Difficulty of Solving Cryptographic Primitive Problems Related to the Discrete Logarithm Problem(Public Key Cryptography)(Cryptography and Information Security)
- Complexity Analysis of the Cryptographic Primitive Problems through Square-Root Exponent(Discrete Mathematics and Its Applications)
- 退化的グラフの全彩色
- 部分k-木の全彩色を求める線形時間アルゴリズム
- 部分k-木の全彩色を求める多項式時間アルゴリズム
- 情報の漏れを許容する知識の対話証明 (情報セキュリティ)
- SLPに基づく強RSA仮定とDDH仮定の分離 (情報セキュリティ)
- 情報の漏れを許容する知識の対話証明 (ライフインテリジェンスとオフィス情報システム)
- SLPに基づく強RSA仮定とDDH仮定の分離 (ライフインテリジェンスとオフィス情報システム)
- カードの配布による鍵集合プロトコルが最適であるための必要十分条件
- 情報の漏れを許容する知識の対話証明(一般,情報セキュリティ,ライフログ活用技術,ライフインテリジェンス,オフィス情報システム,一般)
- SLPに基づく強RSA仮定とDDH仮定の分離(一般,情報セキュリティ,ライフログ活用技術,ライフインテリジェンス,オフィス情報システム,一般)
- 情報の漏れを許容する知識の対話証明(一般,情報セキュリティ,ライフログ活用技術,ライフインテリジェンス,オフィス情報システム,一般)
- SLPに基づく強RSA仮定とDDH仮定の分離(一般,情報セキュリティ,ライフログ活用技術,ライフインテリジェンス,オフィス情報システム,一般)
- 情報の漏れを許容する知識の対話証明
- SLPに基づく強RSA仮定とDDH仮定の分離
- 学習支援や授業ふり返りのための板書レクチャーの簡易コンテンツ化(映像(2),五感メディアの品質,コミュニケーションデザイン,画像符号化,食メディア,一般)
- 学習支援や授業ふり返りのための板書レクチャーの簡易コンテンツ化(映像(2),五感メディアの品質,コミュニケーションデザイン,画像符号化,食メディア,一般)
- SLPに基づく強RSA仮定とDDH仮定の分離
- 情報の漏れを許容する知識の対話証明