NEXP

From Традиция
Jump to navigation Jump to search

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

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

N E X P c > 0 N T I M E ( 2 n c ) {\cal NEXP} \equiv \cup_{c>0} {\cal NTIME}(2^{n^c})


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