指数時間仮説とは？わかりやすく解説

辞書 類語・対義語辞典 英和・和英辞典 日中中日辞典 日韓韓日辞典 古語辞典

その他の辞書▼
- 手話辞典
- インドネシア語辞典
- タイ語辞典
- ベトナム語辞典

Weblio 辞書ヘルプ

556の専門辞書や国語辞典百科事典から一度に検索!

無料の翻訳ならWeblio翻訳！

初めての方へ参加元一覧

Weblio 辞書 > 辞書・百科事典 > 百科事典 > 指数時間仮説の意味・解説

ウィキペディア

索引トップ用語の索引ランキングカテゴリー

指数時間仮説

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2015/06/29 05:23 UTC 版)

計算複雑性理論において、指数時間仮説(Exponential time hypothesis)はまだ証明されていない計算量に関する予想であり、Impagliazzo & Paturi (1999)によって定式化された。この予想は、3-SAT(あるいは他のNP完全問題)は最悪ケースにおいて準指数時間（英語版）では解けないというものである。^[1] 指数時間仮説がもし成立すれば、P ≠ NPも成立する。この予想は、多くの計算機科学の問題の計算量が同等である(どれか一つに準指数時間のアルゴリズムが見つかれば、その他すべての問題にも準指数時間のアルゴリズムがある)ことを示すのに使われる。

^ Woeginger (2003).
^ Flum & Grohe (2006).
^ Dantsin & Wolpert (2010).

[続きの解説]

「指数時間仮説」の続きの解説一覧

1 指数時間仮説とは
2 指数時間仮説の概要

松村謙三 (実業家)

名護市女子中学生拉致殺害事件

>> 「指数時間仮説」を含む用語の索引
指数時間仮説のページへのリンク

辞書ショートカット

1 ウィキペディア

カテゴリ一覧

＋ビジネス

＋業界用語

＋コンピュータ

＋自動車・バイク

＋船

＋建築・不動産

＋ヘルスケア

＋スポーツ

＋辞書・百科事典

すべての辞書の索引

Weblioのサービス

「指数時間仮説」の関連用語

1

数学上の未解決問題

百科事典

6% |||||

指数時間仮説のお隣キーワード

指数 (初等整数論)

指数 (経済)

指数型分布族

指数層系列

指数時間仮説

指数関数の原始関数の一覧

指数関数時間

検索ランキング

指数時間仮説のページの著作権
Weblio 辞書情報提供元は参加元一覧にて確認できます。

All text is available under the terms of the GNU Free Documentation License.
この記事は、ウィキペディアの指数時間仮説 (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。

ビジネス｜業界用語｜コンピュータ｜電車｜自動車・バイク｜船｜工学｜建築・不動産｜学問
 文化｜生活｜ヘルスケア｜趣味｜スポーツ｜生物｜食品｜人名｜方言｜辞書・百科事典

ご利用にあたって

・Weblio辞書とは

・検索の仕方

・利用規約

・プライバシーポリシー

・サイトマップ

便利な機能

・ウェブリオのアプリ

・画像から探す

お問合せ・ご要望

・お問い合わせ

会社概要

・公式企業ページ

・会社情報

・採用情報

ウェブリオのサービス

・Weblio 辞書

・類語・対義語辞典

・英和辞典・和英辞典

・Weblio翻訳

・日中中日辞典

・日韓韓日辞典

・フランス語辞典

・インドネシア語辞典

・タイ語辞典

・ベトナム語辞典

・古語辞典

・手話辞典

・IT用語辞典バイナリ

・おすすめのプログラミングスクール情報「Livifun」

©2024 GRAS Group, Inc.RSS