Изменения

Классы EXP, NEXP. Полнота языков EXP и NEXP

216 байт убрано, 13:42, 17 июня 2010

Нет описания правки

====Доказательство====

~~Полной задачей в <tex>NEXP</tex> является задача <tex>BH_{2,N}</tex>(binary nondeterministic bounded halt):~~

~~<tex>BH_{2,N} =\{ \langle m, x, t \rangle \mid m(x) = 1, T(m,x) \le t \}</tex>~~

53

правки