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

Эй, ребята, я понимаю, что уловка заполнения позволяет нам переводить классы сложности вверх - например, . Заполнение работает, «раздувая» ввод, выполняя преобразование (скажем, от к ), что приводит к «волшебному» алгоритму, который вы можете запустить на дополненном вводе. Хотя это имеет технический смысл, я не могу понять, как это работает. Что именно здесь происходит? Есть ли простая аналогия для того, что такое padding?$P=NP \rightarrow EXP=NEXP$$NP$$P$

Может привести здравый смысл, почему это так?

Я думаю, что лучший способ получить интуицию в этом вопросе - подумать о том, каковы полные задачи для экспоненциальных временных классов. Например, полными задачами для NE являются стандартные NP-полные задачи на кратко описываемых входных данных, например, если дана схема, описывающая матрицу смежности графа, является ли граф 3-раскрашиваемым? Тогда проблема того, станет ли E = NE, становится эквивалентной решению задач NP за полиномиальное время на кратко описываемых входах, например, с малой эффективной колмогоровской сложностью. Это, очевидно, не сильнее, чем то, разрешимы ли они на всех входах. Чем больше временная граница, тем меньше колмогоровская сложность соответствующих входных данных, поэтому при больших временных ограничениях коллапсируют действующие алгоритмы, которые работают на меньших подмножествах входных данных.

Рассел Импальяццо

Итак, ваша цель - показать, что на основе (мы не не будем указывать, что именно это за классы, мы просто знаем, что они как-то параметризованы с размером ввода). У нас есть язык , решил какой - то алгоритм . Теперь мы создаем язык , добавляя каждое слово в , так что его длина теперь равна , и мы видим, что оно содержится в (наш новый алгоритм основном просто игнорирует добавленные нули и запускает на реальном, коротком входе).C L A S S 1 [ g ( n ) ] = C L A S S 2 [ h ( n ) ] L ∈ C L $CLASS_1[g(f(n))] = CLASS_2[h(f(n))]$$CLASS_1[g(n)] = CLASS_2[h(n)]$A L ′ x ∈ L f ( n ) C L A S S 1 [ g ( n ) ] A ′$L \in CLASS_1[g(f(n))]$$A$$L'$$x \in L$$f(n)$$CLASS_1[g(n)]$$A'$$A$

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

Теперь мы знаем, что и, следовательно, (определяется по некоторому алгоритму ). Мы бы хотели добраться отсюда до . Но это просто - алгоритм решающий просто дополняет ввод соответствующим образом и запускает на дополненном вводе.L ′ ∈ C L A S S 2 [ h ( n ) ] B ′ L ∈ C L A S S 2 [ h ( f ( n ) ) ] B L B $L' \in CLASS_1[g(n)]$$L' \in CLASS_2[h(n)]$$B'$$L \in CLASS_2[h(f(n))]$$B$$L$$B'$

Этот шаг можно резюмировать следующим образом: мы хотим выбрать в большем, более изобретательном классе. Используя наши дополнительные ресурсы, мы дополняем ввод и запускаем алгоритм, определяющий язык дополнения$L$ .

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

Я вижу аргументы заполнения с точки зрения компактности представления. Подумайте о двух машинах-переводчиках Тьюринга: взрывает экземпляры, а C снова сжимает их.$B$$C$

Аргумент padding работает с , составляя B с детерминированной версией TM для языка нижнего недетерминированного класса. Выходы B вместе образуют язык, который не представлен компактно, так что это становится «легче».$B$$B$$B$

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

Чтобы сделать его более понятным, давайте посмотрим на то, что происходит более абстрактно!

У нас есть два преобразования, одно для входных данных и одно для задач. Я буду обозначать их оба через , из контекста будет ясно, когда это первое, а когда - второе.$pad$

Эти два преобразования имеют следующее свойство:

I. для всех задач , для всех входов x ∈ Σ ∗ :$A\subseteq \Sigma^{ * }$$x\in\Sigma^{ * }$

тогда и только тогда, когда x ∈ A ,$pad(x) \in pad(A)$$x \in A$

II. если находится в E X P ( N E X P ), то p a d ( A ) находится в P ( N P ).$A$$EXP$$NEXP$$pad(A)$$P$$NP$

III. преобразование для входов находится в классе сложности ,$EXP$

Понятно, что преобразования для заполнения имеют эти свойства.

$EXP$$P$$NEXP$$NP$

У меня нет формального аргумента, почему в настоящее время нет таких преобразований, но интуитивно то, что Андраш Саламон сказал правильно. Легко увеличить размер входов, но не понятно, как их можно сжать?

$P=NP$$NEXP=NTime(2^{n^{O(1)}})$$x$$n$$N=2^{n^{O(1)}}$

$NEXP(n) = NTime(2^{n^{O(1)}}) = NTime(N) \subseteq NP(N) \subseteq P(N) = Time(N^{O(1)}) = Time(2^{n^{O(1)}}) = EXP(n)$