Есть ли вычислительная проблема, которая находится в квазиполиномиальном времени, но (возможно) не в

Квазиполиномиальное время, или сокращенно QP, является классом сложности на детерминированной машине Тьюринга. Вот точное определение: https://complexityzoo.uwaterloo.ca/Complexity_Zoo:Q#qp

В то время как βP является классом сложности ограниченного недетерминизма. Вот точное определение: https://complexityzoo.uwaterloo.ca/Complexity_Zoo:B#betap

Легко видеть, что любая машина βP может быть смоделирована машиной QP, а именно βP $\subseteq$ QP.

Но есть ли у нас пример, проблема в QP, но не в βP, даже если у нас просто нет точного доказательства того, что проблема не в βP?

Пока я не знаю конкретного (предполагаемого) примера в $QP-\beta P$есть еще достаточно убедительные доказательства того, что $\beta P$является надлежащим подмножеством$QP$, А именно, эти классы ведут себя очень по-разному в их отношении к$NP$:

$\bullet$ Из определения очевидно, что $\beta P\subseteq NP$,

$\bullet$ С другой стороны, $QP\subseteq NP$ неизвестно, и это было бы очень трудно доказать, так как это подразумевает $P\neq NP$, (На самом деле, это даже более сильное утверждение, чем$P\neq NP$.)

Такое совсем другое поведение по отношению к $NP$ кажется, дает достаточно веские основания полагать, что $\beta P\neq QP$,

Да. У нас такая проблема. Это проблема изоморфизма графа. Бабай доказал, что GI находится в QP . Насколько я понимаю, доказательство Бабая не дает ограниченной верхней границы недетерминизма ($\beta P$) по сложности Г.И.

У нас нет доказательств того, что GI находится в$\beta P$, Кроме того, у нас нет доказательств того, что GI не может быть решена с помощью полилогарифмического недетерминизма.

Смотрите этот пост .

Этот пост в CS Theory от @Salamon указывает на то, что мы даже не знаем, можно ли решить GI с ограниченным квадратным недетерминизмом, не говоря уже о логарифмическом недетерминизме.