多価関数における自己帰着とmany-one型帰着について(情報通信基礎サブソサイエティ合同研究会)
スポンサーリンク
概要
- 論文の詳細を見る
本稿では,多価関数のクラスにおける自己帰着とmany-one型帰着の関係について考察する.結果として,parsimonious(many-oneまたはmetric many-one)帰着に関するすべてのNPMV(またはNPMV_g)完全関数がTuring length-decreasing self-reducibleならば,NPMV(またはNPMV_g)に属するすべての関数に対して,多項式時間計算可能な洗練が存在することを示した.このことは,P≠NPである限り,NPMV(またはNPMV_g)完全かつTuring length-decreasing self-reducibleでない関数が存在することを意味している.
- 2011-02-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型帰着について(情報通信基礎サブソサイエティ合同研究会)
- 多価関数における自己帰着と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仮定の分離(一般,情報セキュリティ,ライフログ活用技術,ライフインテリジェンス,オフィス情報システム,一般)
- 1ビットの鍵共有に必要十分なカード配布枚数について
- 情報の漏れを許容する知識の対話証明
- SLPに基づく強RSA仮定とDDH仮定の分離
- 学習支援や授業ふり返りのための板書レクチャーの簡易コンテンツ化(映像(2),五感メディアの品質,コミュニケーションデザイン,画像符号化,食メディア,一般)
- 学習支援や授業ふり返りのための板書レクチャーの簡易コンテンツ化(映像(2),五感メディアの品質,コミュニケーションデザイン,画像符号化,食メディア,一般)
- 最短なオイラー閉路状鍵共有
- 最小枚数のカードの配布によるオイラー閉路状鍵共有
- カードの配布によるオイラー閉路状鍵共有
- カードの配布を用いた受領確認可能な鍵共有プロトコル
- 情報理論的に安全で受領確認可能な鍵共有法
- SLPに基づく強RSA仮定とDDH仮定の分離
- 情報の漏れを許容する知識の対話証明