Вокруг множество проблем с NP-полнотой, и источники их собирают, например, см. Книгу Гэри и Джонсона. Мне было бы интересно увидеть список неполных NEXP задач. Есть ли один доступный? Поскольку я предполагаю, что нет, я открываю этот вопрос (это должна быть вики сообщества? Я не знаю об этом...
Возможно ли, что ? Есть ли интересные последствия такого сдерживания? Будет ли это противоречить гипотезе экспоненциального времени?SAT¯¯¯¯¯¯¯¯¯¯∈NTIME(exp(n0.9))SAT¯∈NTIME(exp(n0.9))\overline{SAT} \in...
У меня есть проблема, которая находится в NEXP и также может быть решена с помощью чередующегося ТМ, использующего экспоненциальное время и только одно чередование (начиная с экзистенциального состояния).NPNP^{\text{NP}} Что-нибудь известно о NEXP ? Это равно NEXP или какому-то другому классу?...
Имеет ли означают E = N E