Изменения

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

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

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

== Полная задача в классе ''EXP'' ==

~~===~~ Существует полная в ''EXP'' задача ~~===~~

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

== Полная задача в классе ''NEXP'' ==

~~===~~ Существует полная в ''NEXP'' задача ~~===~~

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

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

53

правки