E (التعقيد)

في نظرية التعقيد الحسابي ، فإن فئة التعقيد E هي مجموعة مشاكل القرار التي يمكن حلها بواسطة آلة تورينج حتمية في وقت 2 ^{O ( n )} وبالتالي فهي تساوي فئة التعقيد DTIME (2 ^{O ( n )} ).

E ، على عكس الفئة المماثلة EXPTIME ، ليست مغلقة تحت عمليات الاختزال متعددة الواحدات ذات الوقت متعدد الحدود .

E موجودة في NE .

• أليندر، إي.؛ شتراوس، م. (1994)، "مقياس على فئات التعقيد الصغيرة مع تطبيقات لـ BPP"، وقائع مؤتمر IEEE FOCS'94 ، الصفحات 807-818 ، ECCC TR94-004 ، DIMACS TR 94-18  .
• بوك، ر. (1972)، "حول اللغات المقبولة في وقت متعدد الحدود"، مجلة SIAM للحوسبة ، 1 (4): 281-287 ، doi : 10.1137/0201019.
• بوك، ر. (1974)، "مقارنة فئات التعقيد"، مجلة علوم الحاسوب والأنظمة ، 3 (9): 213-229 ، doi : 10.1016/s0022-0000(74)80008-5.
• إمباغليازو، ر .؛ تاردوس، ج. ( 1989)، "مسائل القرار مقابل مسائل البحث في وقت متعدد الحدود الفائق"، وقائع مؤتمر IEEE FOCS 1989 ، الصفحات 222-227 .
• واتانابي، أو. (1987)، "مقارنة مفاهيم اكتمال الوقت متعدد الحدود"، علوم الحاسوب النظرية ، 54 ( 2-3 ): 249-265 ، doi : 10.1016/0304-3975(87)90132-0.

• حديقة الحيوانات المعقدة : الفئة هـ