Почему проблемы NPI не все одинаковой сложности?

Как можно взглянуть на проблему и причину, по которой это скорее NP-Intermediate, чем NP-Complete? Часто довольно просто взглянуть на проблему и сказать, является ли она NP-Complete или нет, но мне кажется, что гораздо сложнее определить, является ли проблема NP-Intermediate, так как грань между ними кажется довольно тонкой. классы. По сути, я спрашиваю, почему проблема, которая может быть проверена за полиномиальное время (если она вообще существует), но не решена за полиномиальное время (если P dos не равна NP), не будет сводиться за полиномиальное время друг к другу. Кроме того, есть ли способ показать, что проблема NP-Intermediate аналогична тому, как показано, что проблема NP-Hard, например редукция или какой-либо другой метод? Будем благодарны за любые ссылки или учебники, которые помогут мне понять класс NP-Intermediate.

Вы не можете показать , что проблема является без разделения P от N P .$\mathsf{NPI}$$\mathsf{P}$$\mathsf{NP}$

Есть искусственные проблемы , которые могут быть доказаны , чтобы быть в с использованием обобщения теоремы Ландера (также см это ) при условии , что N P ≠ P .$\mathsf{NPI}$$\mathsf{NP}\neq\mathsf{P}$

Также проложенный версия проблем являются Н Р $\mathsf{NEXP\text{-}complete}$$\mathsf{NPI}$ предполагая , (смотри также это и это ).$\mathsf{NEXP} \neq \mathsf{EXP}$

Проблемой в часто считается N P I, когда:$\mathsf{NP}$$\mathsf{NPI}$

1. при разумных допущениях мы можем показать, что это не но неизвестно, что он находится в P ,$\mathsf{NPC}$$\mathsf{P}$

2. при разумных допущениях мы можем показать, что его нет в но неизвестно, что он находится в N P C ,$\mathsf{P}$$\mathsf{NPC}$

и когда - то только тогда , когда мы не можем показать , что в или P .$\mathsf{NPC}$$\mathsf{P}$

Примером разумного предположения является экспоненциальная гипотеза времени (или некоторые другие предположения о вычислительной жесткости ).

По сути, я спрашиваю, почему проблема, которая может быть решена за полиномиальное время (если она вообще существует), но не решена за полиномиальное время (если P не равен NP), не будет сводиться за полиномиальное время друг к другу.

$\mathsf{NPC}\not \subseteq \mathsf{P}$П Н $\mathsf{P}$$\mathsf{P}$$\mathsf{NP}$

Типичный случай, когда проблема в также лежит в или . Предполагая, что полиномиальная иерархия не разрушается, такая проблема не может быть -полной. Примеры включают целочисленную факторизацию, дискретный логарифм, изоморфизм графов, некоторые задачи решетки и т. Д.с о Н П с о А М Н $\mathsf{NP}$$\mathsf{coNP}$$\mathsf{coAM}$$\mathsf{NP}$

Другой типичный случай проблемы - когда есть свидетель длины но меньше, чем . Проблема существования клики размером в графе является типичным примером - в этом случае свидетель (конкретная клика) требует битов.ω ( log n ) n O ( 1 ) log n O ( log 2 n $NPI$$\omega(\log n)$$n^{O(1)}$$\log n$$O(\log^2 n)$

Принимая гипотезу об экспоненциальном времени, такая проблема проще, чем полная задача (которая требует времени )), но сложнее, чем проблема полиномиального времени.exp ( n O ( 1 )$NP$$\exp(n^{O(1)})$