Имеет ли

Имеет ли означают ? $\mathsf{EXP}=\mathsf{NEXP}$ $\mathsf{E}=\mathsf{NE}$

cc.complexity-theory conditional-results nexp structural-complexity argentpepper
источник

Да, E = NE подразумевает EXP = NEXP, что может быть доказано с помощью аргумента заполнения.

Мухаммед Аль-Туркистани

Для меня не очевидно, почему EXP = NEXP подразумевает E = NE. Если это так, то любой алгоритм

для Succinct3SAT можно преобразовать в алгоритм

для Succinct3SAT. Может быть, вы все изменили, и вы хотели спросить о другом значении?

2^{n^{k}}

$2^{n^k}$

2^{O (n)}

$2^{O(n)}$

Райан Уильямс

И тогда P = NP, если P = 0 или N = 1!

Даниэль Апон

Да. Я думаю, это проблема с домашним заданием.

Мухаммед Аль-Туркистани

Я не понимаю закрытие этого вопроса как «ненастоящего вопроса» после того, как он был отредактирован до разумного вопроса (хотя формулировка вопроса не интересна). Например, комментарий Райана Уильямса может быть ответом на него.

Цуёси Ито

Ответы:

Это открыто, насколько я знаю. Это может быть доказуемо (потому что его гипотеза может быть ложной) или просто трудно показать, что любой алгоритм для Succinct3SAT можно преобразовать в алгоритм для Succinct3SAT. $2^{n^k}$ $2^{O(n)}$

В общем, теоремы такого типа называются «коллапсами вниз», которые говорят, что если два «больших» класса равны, то два «меньших» класса равны. Эти теоремы редки. Обычно вы можете либо доказать «восходящий коллапс» (маленькие равные классы означают более крупные классы, равные, как подразумевает ), либо его противоположное, «разделение вниз». $P = NP$ $NEXP = EXP$

То, что вам нужно, - это теорема Хартманиса, Иммермана и Сьюелсона ( http://dl.acm.org/citation.cfm?id=808769 ), что $NE = E$ $\iff$ каждое разреженное множество в содержится в . Это дает «нисходящий коллапс», но только для разреженных множеств (тех множеств, которые содержат только строк длины ). $NP$ $P$ $poly(n)$ $n$

Райан Уильямс
источник