Доказательство нижних границ, доказывая верхние оценки

29

Недавний результат оценки нижнего предела сложности схемы Райана Уильямса предоставляет метод доказательства, который использует результат верхнего предела для доказательства нижних границ сложности. Суреш Венкат в своем ответе на этот вопрос : есть ли какие-то противоречивые результаты в теоретической информатике? , предоставил два примера установления нижних границ путем доказательства верхних границ.

  • Каковы другие интересные результаты для доказательства нижних оценок сложности, которые были получены путем доказательства верхних оценок сложности?

  • Существует ли какая-либо гипотеза верхней границы, которая подразумевает (или P \ ne NP )?NPP/polyPNP

Мухаммед Аль-Туркистани
источник
Должно ли это быть CW?
Мухаммед Аль-Туркистани
Мне нравится, как есть (не CW), но я считаю, что это [soft-question].
MS Dousti
2
@ Садек: не думайте, что это мягкий вопрос, это достаточно точно, чтобы иметь четкий ответ.
Каве
Результат Мейера, на который указывает Суреш, показывает, что существование полиномиальных цепей для доказало бы P \ ne NP . EXPPNP
Мухаммед Аль-Туркистани

Ответы:

23

Можно перевернуть вопрос и спросить, какие нижние оценки не доказаны, доказав верхнюю оценку. Почти все нижние границы сложности связи (и нижние границы алгоритма потоковой передачи и нижние границы структуры данных, которые основаны на аргументах сложности связи) подтверждаются показом того, что протокол связи можно конструктивно превратить в схему кодирования, причем длина кодирования зависит от коммуникационная сложность протокола, а нижняя граница для протокола следует из того факта, что вы не можете кодировать все n-битные сообщения, используя n-1 бит или меньше.

Нижние границы цепей Разборова-Смоленского показывают, как имитировать схемы с ограниченной глубиной полиномами низкой степени.

Парой кандидатов нижних границ, которые не доказаны верхней границей, могут быть теорема иерархии времени (хотя, чтобы получить самые жесткие оценки, требуется эффективная универсальная машина Тьюринга, которая является нетривиальной алгоритмической задачей) и доказательство нижних оценок AC0 с использованием леммы о переключении (но самое чистое доказательство леммы о переключении использует подсчет / несжимаемость / сложность Колмогорова)

Лука Тревизан
источник
1
Интересно, что это отличная сводка нижних границ сложности общения! Другой (странный?) Кандидат: теорема Ладнера / диагонализация. Границы, конечно, не указаны (и даже не проблема (ы)!), Но она показывает суперполиномиальную нижнюю оценку для некоторой задачи. Конечно, это предполагает P NP, что можно было бы доказать с верхней границей, а-ля GCT ...
Даниэль Апон
14

Странным образом, сама теорема PCP является хорошим примером доказательства нижней границы через верхнюю оценку. «Эффективная» рандомизированная стратегия проверки доказательства с использованием постоянного числа проб доказательства и только случайных бит приводит к нижней границе для аппроксимации числа удовлетворенных предложений в экземпляре 3SAT.logn

Суреш Венкат
источник
10
Если вы считаете NP-твердость (в отличие от отделения от класса) нижними границами, вам не нужна теорема PCP; сокращения - эффективные алгоритмы, которые доказывают, что некоторые проблемы трудны.
Цуёси Ито
это хорошая мысль, Цуеши. Тем не менее, снижение твердости NP является «прямым». показать, что решение неизвестной проблемы решает известную сложную проблему. Некоторые из приведенных здесь примеров являются более косвенными. Но это субъективно конечно.
Суреш Венкат
3
Самым утверждением теоремы PCP является NP-полнота Gap-3SAT. Более того, я не знаю, что вы имели в виду, утверждая, что теорема PCP является косвенной. Это правда, что теорема PCP требует одного из самых сложных доказательств среди результатов NP-полноты, но хорошо ли это?
Цуёси Ито
Суреш, не могли бы вы опубликовать здесь, в качестве нового ответа, расширенную версию двух примеров, на которые вы ссылались в ответе на другой вопрос (результат Мейера и GCT)?
Мухаммед Аль-Туркистани
какая причина почему? У меня нет проблем с этим, но нужно ли это, поскольку вы привели это в вопрос?
Суреш Венкат
12

Метод несжимаемости - это метод, основанный на колмогоровской сложности для доказательства нижних оценок. Одним из первых применений этого метода было доказать, что распознавание палиндромов на машине Тьюринга с одной лентой требует квадратичного времени.

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

Конечно, полную информацию можно найти в учебнике Ли и Витани .

Марк
источник
11

Для вопроса «нижняя граница через верхнюю границу» вы задали:

Статья STOC 2010 «Как сжать интерактивное общение» [BBCR10] приводит к усовершенствованной теореме о прямой сумме для рандомизированной сложности связи, демонстрируя улучшенный протокол сжатия для интерактивного общения.

CIO~(CI)

fnkfkn

Даниэль Апон
источник
7

Это как-то отличается от того, что вы просили, но, поскольку это связано, я подумал, что могу это упомянуть.

Carter & Wegman (1977) ввели понятие универсального хеширования . Это понятие использовалось во многих работах ( Sipser (1983) , Stockmeyer (1983) , Babai (1985) и Goldwasser & Sipser (1986) ), чтобы доказать приблизительные нижние оценки .

Это было до 1987 года, когда Fortnow использовал универсальное хеширование для доказательства приблизительных верхних границ . (На самом деле, чтобы предоставить протокол для доказательства приблизительных верхних границ.)


Редактировать:

Это не нижние результаты, но они могут быть полезны в любом случае:

NPP/polyPH=Σ2p=Π2p

NPP/polyAM=MA

coNPNP/polyPH=Σ3p=Π3p

М.С. Дусти
источник
5

PNP

CC1Cm

PNP

Мухаммед Аль-Туркистани
источник
5

Вот пример из «Вычислительная сложность: современный подход» Ароры и Барака (стр. 128):

EXPo(2n/n)PNP

Мухаммед Аль-Туркистани
источник