Естественные кандидаты в NP-E и E-NP

10

С начала 70-х годов известно, что и не равны (потому что не является замкнутым в полиномиальном времени многих одно сокращение, в отличие от ). Однако, насколько мне известно, до сих пор не ясно, является ли один класс подмножеством другого, или они несопоставимы, то есть и оба непусты.NPE=DTIME(2O(n))ENPNPEENP

Вопрос: Какие (желательно естественные) проблемы являются кандидатами на участие в или , если предположить, что соответствующий набор не пуст? Меня особенно интересуют естественные проблемы внутри которые, вероятно, требуют экспоненциального времени с суперлинейным показателем, то есть они находятся в .NPEENPNPNPE

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

Ответы:

15

TQBF (истинные количественные булевы формулы) находится в E и не будет в NP, если NP = PSPACE.

Язык в NP-E сложнее. Такой язык также был бы в NP-NTIME (n), и у нас нет хороших примеров этого. Вы могли бы использовать сжатое представление как

L={C |  Circuit описывает граф на узлах, где 3-раскрашивается .CG|C|5G}

L в NP, вряд ли в но не так естественно.E

Лэнс Фортноу
источник