E (complexity)

ウィキペディア

E (計算複雑性理論)

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/10/22 01:49 UTC 版)

計算複雑性理論において複雑性クラス E とは、決定性チューリング機械で 2^O(n) の時間で解ける決定問題の集合である。これはすなわち、複雑性クラス DTIME(2^O(n)) に等しい。

E は類似のクラス EXPTIME よりも理論上の重要性が低いとされる。それは、多項式時間多対一還元において閉じていないためである。

参考文献

• E. Allender and M. Strauss. Measure on small complexity classes with applications for BPP, Proceedings of IEEE FOCS'94, pp. 807-818, 1994. ECCC TR94-004, DIMACS TR 94-18.
• R. Book. On languages accepted in polynomial time, SIAM Journal on Computing 1(4):281-287, 1972.
• R. Book. Comparing complexity classes, Journal of Computer and System Sciences 3(9):213-229, 1974.
• R. Impagliazzo and G. Tardos. Decision versus search problems in super-polynomial time, in Proceedings of IEEE FOCS 1989, pp. 222-227, 1989.
• O. Watanabe. Comparison of polynomial time completeness notions, Theoretical Computer Science 53:249-265, 1987.

外部リンク

• E at the Complexity Zoo

Weblio日本語例文用例辞書

「E (complexity)」の例文・使い方・用例・文例

• EXシアター六本木前です。降りるときに教えてあげます。
• 今年の1 月まで、「Premiumアイスクリーム」で知られるErnesto Dairyの副社長だったCarla Starkが、4 月20 日付けでHolman Health社の会長に就任することが今日発表された。
• Holman Healthの株主は、StarkがErnestoに行ったのと同じ魔法をかけてくれることを大いに期待していると報じられている。Starkは、Ernestoがグルメアイス市場において驚くべき20％というシェアを獲得することになった「Premiumアイスクリーム」のブランドを作り上げた人物である。
• Holman Healthを辞職し、Ernesto Dairyに勤めるつもりである。
• クローゼットの解決策のNo. 1 オンライン販売業者、CUSTOM CLOSETSは、オンラインショッピングサービスのリニューアルを発表します！
• CUSTOM CLOSETSは製造会社である。
• CUSTOM CLOSETSは助言をしない。
• CUSTOM CLOSETSで売られているものは、ほかのところではより安い。
• セミナーに関する詳細は、4 月10 日までに全スタッフにEメールで送信されます。
• 一部の社員がキャリアに関するEメールを受け取る。
• 議題リストの案をこのEメールに添付しました。
• 興味のある方は、12月5日までに、履歴書と少なくとも2通の職務に関する推薦状を添付したEメールを、Singh金融サービスのMisa Takahama、mtakahama@singhfs.comまで送ってください。
• 面接を行う予定だった、営業部長のDon Richmanが、家庭の事情で突然呼び出されたことをお知らせするために、Eメールを差し上げています。
• その経済誌の最新号に当社のCEOが載っています。
• 誤解があるといけないので、10 月12 日の最終交渉の際に、初回納品日が1 月10 日から1 月5 日に変更されたことを、このEメールではっきりさせておきたいと思います。
• 特定の商品の価格見積もりをご希望の場合は、Eメールでお問い合わせください。
• いつもBOSCO TECHの商品をお引き立ていただき、ありがとうございます。
• 弊社の最新の衝撃吸収ジェルシート商品、MEGA GELの発売を発表できることを誇りに思います。
• BOSCO TECHは今後も製品の品質と革新に専心して参ります。そして、それこそがスマートフォンから薄型テレビまであらゆるものを保護する製品、MEGA GELでお伝えするものです。
• MEGA GELは、保護のための製品である。