не-NP

[ShMaxG]

Существуют ли языки, не принадлежащие NP? Если да, то как это доказать? Спрашиваю из чистого любопытства, хотелось бы лишь качественное объяснение. То, что это можно найти в какой-нибудь книге - понимаю, но расчитаны они, я думаю, только для специалистов. Гуглил, но не нашел ничего интересного.

[Xaositect]

ShMaxG в сообщении #239120 писал(а):

Существуют ли языки, не принадлежащие NP? Если да, то как это доказать? Спрашиваю из чистого любопытства, хотелось бы лишь качественное объяснение. То, что это можно найти в какой-нибудь книге - понимаю, но расчитаны они, я думаю, только для специалистов. Гуглил, но не нашел ничего интересного.

http://en.wikipedia.org/wiki/Quantified ... la_problem является $\textrm{PSPACE}$-полной задачей и не лежит в $\textrm{NP}$, если $\textrm{NP}\neq \textrm{PSPACE}$(это не доказано).

[ShMaxG]

Xaositect в сообщении #239131 писал(а):

и не лежит в $\textrm{NP}$, если $\textrm{NP}\neq \textrm{PSPACE}$(это не доказано).

Так это "если". А хотелось бы реального примера док-ва, когда точно известно, что не-NP.

[Xaositect]

Существует также задачи, которые не лежат в $\mathrm{NP}$ и без недоказанных предположений.
Например, распознавание доказуемости в арифметике Пресбургера (http://en.wikipedia.org/wiki/Presburger_arithmetic) имеет временную сложность не менее $2^{2^{cn}}$, значит, не лежит в $\mathrm{PSPACE}$ и, следовательно, $\mathrm{NP}$

[ShMaxG]

Посмотрел, спасибо

[Профессор Снэйп]

ShMaxG в сообщении #239120 писал(а):

Существуют ли языки, не принадлежащие NP?

??? Существует континуум различных языков и лишь счётное число не то, что NP-языков, а даже просто разрешимых (распознаваемых машиной Тьюринга за конечное время).

Или нужен пример какого-нибудь "естественного" языка?

[ShMaxG]

Профессор Снэйп
Ага, "естественного". И на пальцах как примерно доказывать то, что не-NP. Вот в примере Xaositect оценку снизу сложности получили. Может еще есть способы?

[Профессор Снэйп]

ShMaxG в сообщении #239329 писал(а):

Профессор Снэйп
Ага, "естественного". И на пальцах как примерно доказывать то, что не-NP. Вот в примере Xaositect оценку снизу сложности получили. Может еще есть способы?

Совсем естественных не знаю. И, насколько я понимаю, вопрос $NP = EXP$ ещё не решён. А естественно возникающие в приложениях языки, как правило, экспоненциальные, так как в худшем случае всё всегда решается тупым перебором

Если же задать себе специальной целью построить не экспоненциальный язык (который, естественно, не попадёт в класс NP), то тут всё очень просто. Обычная диагональка. Для каждой программы $P$ берём машину Тьюринга и включаем сам текст этой программы в язык тогда и только тогда, когда она на входе, равном этому тексту, не даёт ответ "да" за $\leqslant 2^{2^{|P|}}$ шагов.

[ShMaxG]

Профессор Снэйп
Хм, однако, круто.