EXPTIME

Материал из свободной русской энциклопедии «Традиция»
Перейти к: навигация, поиск

EXPTIME — класс задач, разрешимых на машине Тьюринга за экспоненциальное время.

Более формально, через определение класса DTIME:

\({\cal EXPTIME} \equiv \cup_{c>0} {\cal DTIME}(2^{n^c})\)


По крайней мере часть этого текста взята с ресурса http://lib.custis.ru/ под лицензией GDFL.Список авторов доступен на этом ресурсе в статье под тем же названием.