Почему NP в EXPTIME?

Есть ли простой способ понять, почему NP находится в EXPTIME? Мне кажется априори возможным, что может существовать проблема, для решения которой требуется сверхэкспоненциальное время, но решение которой можно проверить за полиномиальное время.

complexity-theory complexity-classes tparker
источник

На самом деле, NP

PSPACE.

\subseteq

$\subseteq$

Добро пожаловать в информатику! Что вы пробовали? Где вы застряли? Мы не хотим просто выполнять вашу (домашнюю) работу за вас; Мы хотим, чтобы вы получили понимание. Однако, поскольку мы не знаем, в чем заключается ваша основная проблема, мы не можем начать помогать. Смотрите здесь для соответствующего обсуждения. Если вы не уверены в том , как улучшить ваш вопрос, почему не поспрашивать в области компьютерных наук в чате ? Вы также можете проверить наши справочные вопросы .

Рафаэль

Любая проблема в NP находится в EXPTIME, потому что вы можете использовать экспоненциальное время, чтобы попробовать все возможные сертификаты, или перечислить все возможные пути вычисления недетерминированной машины.

Более формально, есть два основных определения NP . Во-первых, язык находится в NP, если существует отношение такое что $L$ $R$

существует такой многочлен , что для всех , , $p$ $(x,y)\in R$ $|y|\leq p(|x|)$
учитывая строку , мы можем определить во времени полином от будь то и $x\#y$ $|x\#y|$ $(x,y)\in R$
. $L = \{x\mid (x,y)\in R\}$

Итак, если у нас есть экспоненциальное время, и мы хотим знать, если , мы можем просто попробовать все возможных значений для ~ и посмотрите, если для любого из них. Это занимает время , поэтому $x\in L$ $|\Sigma|^{p(n)}$ $y$ $(x,y)\in R$ $2^{O(p(n))}$ $L\in\,$ ОПЫТ .

В качестве альтернативы, мы можем определить NP как набор языков, определяемых недетерминированными машинами Тьюринга за полиномиальное время. В этом случае предположим, что определяется машиной за время для некоторого полинома для входов длины . Тогда делает не более недетерминированный выбор при определении , если . Изучая функцию перехода , мы можем найти постоянную такую, что имеет не более $L$ $M$ $p(n)$ $p$ $n$ $M$ $p(|x|)$ $x\in L$ $M$ $k$ $M$ недетерминированных вариантов на каждом шаге вычисления (независимо от входных данных), поэтому он имеет не более различных последовательностей недетерминированных вариантов при чтении входных данных . Учитывая экспоненциальное время, мы можем смоделировать каждую из этих возможностей одну за другой и посмотреть, принимает ли какая-либо из них. $k$ $k^{p(|x|)} = 2^{O(p(|x|))}$ $x$

Дэвид Ричерби
источник

Строго говоря, многочлен во втором маркере нужно выбирать раз и навсегда, он не может зависеть от

. ;)

x

$x$

y

$y$

Мартин Бергер

Что такое определение EXPTIME? Я вспоминаю это как

, но ваш ответ, кажется, предполагает

. Не очевидно, что дополнительный многочлен можно включить, не делая его другим классом сложности.

O (k^{| x |})

$O(k^{|x|})$

O (k^{p (| x |)})

$O(k^{p(|x|)})$

kasperd

@kasperd Согласно Википедии, EXPTIME определяется как решение проблем, которые могут быть решены в

O (k^{p (| x |)})

$O(k^{p(|x|)})$

tparker

Почему NP в EXPTIME?

Ответы: