Методы показа этой проблемы в твердости «подвешенный»

Учитывая новую проблему в , истинная сложность которой находится где-то между и являющейся NP-полной, я знаю два метода, которые можно использовать, чтобы доказать, что решить эту проблему сложно:$\mathsf{NP}$$\mathsf{P}$

1. Покажите, что задача является GI-полной (GI = Изоморфизм графов)
2. Покажите, что проблема в . По известным результатам такой результат подразумевает, что если задача является NP-полной, то PH падает на второй уровень. Например, известный протокол для неизоморфизма графов делает именно это.$\mathsf{co-AM}$

Существуют ли какие-либо другие методы (возможно, с разными «убеждениями»), которые были использованы? Для любого ответа необходим пример того, где он фактически использовался: очевидно, есть много способов показать это, но примеры делают аргумент более убедительным.

Показ того, что ваша проблема в coAM (или SZK), действительно является одним из основных способов привести доказательства «неопределенности твердости». Но кроме этого есть несколько других:

• Покажите, что ваша проблема в NP ∩ coNP. (Пример: Факторинг.)
• Покажите, что ваша проблема разрешима за квазиполиномиальное время. (Примеры: измерение VC, приближенные бесплатные игры.)
• Покажите, что ваша задача не сложнее, чем инвертировать односторонние функции или решить NP в среднем. (Примеры: множество проблем в криптографии.)
• Покажите, что ваша проблема сводится к (например) Уникальным играм или Расширению малого набора.
• Покажите, что ваша проблема в BQP. (Пример: Факторинг, хотя, конечно, это также в NP ∩ coNP.)
• Исключите большие классы снижения NP-полноты. (Пример: проблема минимизации цепей, изученная Kabanets и Cai.)

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

$n$

Примером может служить проблема разбиения чисел на k-блоки (из блога Fortnow & Gasarch, первоисточник: Cyberpuzzles доктора Экко ):

{ $\{ (n,k) \mid \text{ there exists a way to partition }$ $\{1,...,n\} \text{ into at most k boxes so that no box has } x,y,z \text{ with } x+y=z \}$

Вот три дополнения к списку Скотта:

• Покажи свою проблему в ракурсе. Это означает, что число решений ограничено некоторым полиномом. (Пример: проблема с шлагбаумом). Ни одна NP-полная проблема, как известно, не существует в P. (невозможно, если только P = NP).
• Покажите вашу проблему в $LOGNP$$NP[log^2n]$
• Покажите, что ваша задача имеет субэкспоненциальную плотность (Х. Берман и Дж. М. Хичкок доказали нижнюю границу плотности ( ), если только иерархия полиномов не разрушится. Следовательно, любое N P -полное множество должно иметь некоторое ϵ > 0 такое, что для бесконечно -много целых чисел $2^{n^{\epsilon}}$$NP$$\epsilon \gt 0$$n\ge 0$$2^{n^{\epsilon}}$$n$

H. Бурман и JM Хичкок, NP-Hard Наборы Экспоненциально Плотные Если только $coNP ⊆ NP/poly$