Является ли НП в

$DTIME(n^{polylogn})$ известен как $QP$ (квазиполиномиальный).

$NP\not \subset QP$ $P\neq NP$

Некоторые общие предположения, такие как гипотеза об экспоненциальном времени, подразумевают . $NP\not \subset QP$

RB
источник

Вы говорите, что «Некоторые общие предположения ...». Какие другие, кроме ETH? Я чрезвычайно заинтересован, потому что в настоящее время я работаю над связью NP и QP - по крайней мере, я на это надеюсь ...

Мэтт Грофф

Еще одна веская причина полагать, что состоит в том, что подразумевает , и последнее считается маловероятным. Это следствие может быть доказано аргументом заполнения, см., Например, в доказательстве предложения 2 в следующей статье: $NP\not\subseteq QP$ $NP\subseteq QP$ $EXP=NEXP$

Х. Берман и С. Гомер, "Суперполиномиальные схемы, почти разреженные оракулы и экспоненциальная иерархия", Основы программных технологий и теоретической информатики, Springer LNCS Vol. 652, 1992, с. 116-127, pdf

Андрас Фараго
источник

Мне очень нравится этот ответ. Учитывая ответ RB, это заставляет меня задаться вопросом, что, если таковые имеются, отношения между ETH и предположения

E X P \neq N E X P

$\mathsf{EXP} \neq \mathsf{NEXP}$

Джошуа Грохов

@ Иисус Навин Я не искал литературу по этому поводу, но, думаю, любое нарушение ETH, вероятно, подразумевает некоторый крах на более высоком уровне. Я думаю, уровень зависит от того, «насколько сильно» нарушен ETH, более сильные нарушения приводят к более драматическим провалам. Как указано в ответе, сильное нарушение ETH из

означает

. Если мы возьмем более легкое нарушение, например предположим, что

находится в субэкспоненциальном классе, большем, чем

, то коллапс, вероятно, сместится вверх (например, в двойные экспоненциальные классы или даже выше).

N P \subseteq Q P

$NP\subseteq QP$

E X P = N E X P

$EXP=NEXP$

N P

$NP$

Q P

$QP$

Андрас Фараго

Thansk, но я спрашивал о прямой причастности либо образом между ETH и

. Теперь у нас есть два ответа - ETH подразумевает

подразумевает

- и мне было любопытно, было ли одно следствием другого.

E X P \neq N E X P

$\mathsf{EXP} \neq \mathsf{NEXP}$

N P ⊈ Q P

$\mathsf{NP} \not\subseteq \mathsf{QP}$

N E X P \neq E X P

$\mathsf{NEXP} \neq \mathsf{EXP}$

N P ⊈ Q P

$\mathsf{NP} \not\subseteq \mathsf{QP}$

Джошуа Грохов

К сожалению, я не осознаю прямых последствий. С другой стороны, весьма интересно, что нарушения ETH могут приводить не только к коллапсу, но и к разделению с точки зрения нижних границ контура. Статья Райана Уильямса (pdf) доказывает, что даже малейшее нарушение ETH подразумевает определенную общеизвестную трудность доказательства нижних границ схемы.

Андрас Фараго

Является ли НП в

Ответы: