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

25

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

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

gabgoh
источник
11
Я хотел бы отметить, что не все результаты класса сложности идут вверх. Например, если вы доказали EXPNEXP , то это будет означать PNP . Как правило, обвалы увеличиваются, а разлуки - снижаются.
Робин Котари
верно. На самом деле, это кажется хорошим способом думать об этом, так как разделение более интуитивно, чем разрушение.
Габго
2
@Robin, @gabgoh: даже некоторые обвалы идут вниз, но не путем дополнения аргументов. Смотрите, например, arxiv.org/abs/cs/9910008 .
Джошуа Грохов

Ответы:

30

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

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

Рассел Импальяццо
источник
14

Итак, ваша цель - показать, что на основе (мы не не будем указывать, что именно это за классы, мы просто знаем, что они как-то параметризованы с размером ввода). У нас есть язык , решил какой - то алгоритм . Теперь мы создаем язык , добавляя каждое слово в , так что его длина теперь равна , и мы видим, что оно содержится в (наш новый алгоритм основном просто игнорирует добавленные нули и запускает на реальном, коротком входе).C L A S S 1 [ g ( n ) ] = C L A S S 2 [ h ( n ) ] L C L ACLASS1[g(f(n))]=CLASS2[h(f(n))]CLASS1[g(n)]=CLASS2[h(n)]A L x L f ( n ) C L A S S 1 [ g ( n ) ] A ALCLASS1[g(f(n))]ALxLf(n)CLASS1[g(n)]AA

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

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

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

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

Каролина Солтыс
источник
13

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

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

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

Андраш Саламон
источник
5

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

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

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

I. для всех задач , для всех входов x Σ :AΣxΣ

тогда и только тогда, когда x A ,pad(x)pad(A)xA

II. если находится в E X P ( N E X P ), то p a d ( A ) находится в P ( N P ).AEXPNEXPpad(A)PNP

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

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

EXPPNEXPNP

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

P=NPNEXP=NTime(2nO(1))xnN=2nO(1)

NEXP(n)=NTime(2nO(1))=NTime(N)NP(N)P(N)=Time(NO(1))=Time(2nO(1))=EXP(n)

Кава
источник
1
N=log(n)
1
Третий способ думать об этом, на самом деле, это смотреть на обратное. Я не придерживался этого подхода до победного конца, но если придет какое-то великое понимание, я опубликую его как ответ самому себе.
Габго
1
N=2nO(1)nNNnN=log(n)
Каве
1
nN=log(n)PNPEXPNEXP
1
N=log(n)