Класс сложности NEXP

11

У меня есть проблема, которая находится в NEXP и также может быть решена с помощью чередующегося ТМ, использующего экспоненциальное время и только одно чередование (начиная с экзистенциального состояния). $^{\text{NP}}$

Что-нибудь известно о NEXP ? Это равно NEXP или какому-то другому классу? Существуют ли полные проблемы, кроме общей (учитывая машину NEXP и слово, она принимает?). $^{\text{NP}}$ $^{\text{NP}}$

cc.complexity-theory reference-request complexity-classes nexp Сянь-Чжи Чан 張顯之
источник

2

Проверьте работу по экспоненциальной иерархии времени, например, ecommons.library.cornell.edu/bitstream/1813/6617/1/86-777.pdf

5501

3

Обратите внимание, что имеет другое имя в литературе (основанное на характеристике чередования), а именно .

N E X P^{N P}

$NEXP^{NP}$

Σ_{2} E X P

$\Sigma_2 EXP$

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

7

Естественная -полная проблема заключается в определении предложения арифметики Пресбургера с префиксом-квантификатором-квантификатором exist (как показано здесь ). Дальнейшие полные проблемы, связанные с теорией баз данных, были изучены здесь . $\text{NEXP}^{\text{NP}}$ $\exists^*\forall^*\exists^*$

Кристоф Хааз
источник

5

(вероятно) больше, чем NEXP, так как мы можем задавать вопросы экспоненциальной длины из оракула. Этот NP во власти там практически NEXP, например. со-Nexp содержится в . $NEXP^{NP}$ $NEXP^{NP}$

domotorp
источник

Вы утверждали также в ответ на ответ Питера Шора , что

, вероятно , строго более мощным , чем

. Я в замешательстве, хотя. Похоже, что аналогично это должно означать, что

больше, чем

, хотя (я думаю) они равны. Куда я здесь не так?

N E X P^{E X P}

$NEXP^{EXP}$

N E X P

$NEXP$

N P^{P}

$NP^P$

N P

$NP$

Гек Беннет

7

@ Huck Полиномы замкнуты относительно полиномов. Экспоненты нет. Таким образом, я могу дать ораку EXP экспоненциально длинный аргумент, и он может работать экспоненциально в этом аргументе, который вдвойне экспоненциальн в исходной задаче.

Марк Рейтблатт

@domotorp Я думал, что

? Как насчет

?

N E X P^{N P} \subseteq N E X P^{E X P} = N E X P

$NEXP^{NP}\subseteq NEXP^{EXP}=NEXP$

E X P^{E X P}

$EXP^{EXP}$

Т ....

Проблема в том, что вход оракула дополняется, например,

.

D T I M E (2^{n})^{D T I M E (2^{n})} = D T I M E (2^{2^{n}})

$DTIME(2^n)^{DTIME(2^n)}=DTIME(2^{2^{n}})$

Домоторп

@ Турбо Я не вижу ошибки сейчас, но похоже, что с помощью этой логики мы могли бы доказать, что для любого

мы имеем

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

f (n)

$f(n)$

D T I M E (f (n)) \subset P / p o l y

$DTIME(f(n))\subset P/poly$

Домоторп

3

Расширяя свой комментарий выше немного: Если у вас есть только один запрос к -oracle (как в вашем случае), то это следует из работы Hemaspaandra, что ваша проблема в . Это означает , что ваша проблема Тьюринг сводится к любой проблемам -Жесткой. Я думаю , что не известно , будет ли это верно для всех . $NP$ $P^{NE}$ $NE$ $NEXP^{NP}$

5501
источник

1

Наибольший запрос машин может сделать к оракулу является экспоненциальным в длине ввода. Сила оракула в этом только полиномиальна, что также должно быть экспоненциальным. Другими словами, . Следовательно, другая машина должна иметь возможность имитировать вашу машину, а также оракула. $NEXP^{NP}$ $poly(2^{n^k})=O(2^{n^{k+1}})$ $NEXP$

Отредактировано для скобок ...

Обри да Кунья
источник

3

НТМ не совсем так работают. НТМ разделяются, и, если одна копия принимает, все принимает. Когда вы разбиваете, вы не можете посмотреть на результаты ваших не детальных копий. Итак, если я сделаю один запрос к машине NP и сразу же верну противоположный ответ, как бы вы смоделировали это?

Марк Рейтблатт

1

N P^{N P}

$NP^{NP}$

N P

$NP$

О да. При моделировании запроса оракула, если правильный результат - нет, тогда все ветви будут возвращать нет. С другой стороны, если правильный результат - «да», то хотя бы одна ветвь вернет «да». В частности, некоторые могут вернуть нет. Таким образом, когда, как предлагает @Mark, вы отменяете результат запроса, вы, скорее всего, получите ложные срабатывания.

Обри да Кунья

Класс сложности NEXP

Ответы: