E (murakkablik) - E (complexity)

Yilda hisoblash murakkabligi nazariyasi, murakkablik sinfi E ning to'plami qaror bilan bog'liq muammolar buni a bilan hal qilish mumkin deterministik Turing mashinasi vaqt ichida 2^{O (n)} va shuning uchun murakkablik sinfiga teng DTIME (2^{O (n)}).

E, shunga o'xshash sinfdan farqli o'laroq MAQSAD, ostida yopilmagan polinom vaqtining ko'p sonli kamayishi.

Adabiyotlar

• Allender, E .; Strauss, M. (1994), "BPP uchun arizalar bilan kichik murakkablik sinflarini o'lchash", IEEE FOCS'94 materiallari, 807-818-betlar, ECCC  TR94-004, DIMACS TR 94-18.
• Kitob, R. (1972), "Polinom vaqtida qabul qilingan tillar to'g'risida", Hisoblash bo'yicha SIAM jurnali, 1 (4): 281–287, doi:10.1137/0201019.
• Kitob, R. (1974), "Murakkablik sinflarini taqqoslash", Kompyuter va tizim fanlari jurnali, 3 (9): 213–229, doi:10.1016 / s0022-0000 (74) 80008-5.
• Impagliazzo, R.; Tardos, G. (1989), "Super-polinom vaqtidagi qidiruv muammolariga qarshi qaror", IEEE FOCS 1989 materiallari, 222-227 betlar.
• Vatanabe, O. (1987), "Polinomlar vaqtining to'liqligi tushunchalarini taqqoslash", Nazariy kompyuter fanlari, 54: 249–265, doi:10.1016/0304-3975(87)90132-0.

Tashqi havolalar

• Murakkablik hayvonot bog'i: E sinf