Барьеры для разделения других классов сложности

9

Влияет ли естественное доказательство , релятивизация и алгебризация на разделение других классов сложности, таких как т. Д.?LNLNPcoNPPHPSPACE

Например, барьер естественных доказательств должен влиять на любое доказательство поскольку он будет отделять . Однако отношения между и , по-видимому, не имеют большого отношения к OWF по сравнению с отношением между и . Так влияют ли естественные доказательства на более сильное разделение ?NPCoNPPNPNPCoNPPNPNPCoNP

Т ....
источник
Я знаю, что верхняя строка статьи ( cs.umd.edu/~gasarch/BLOGPAPERS/natural.pdf ) содержитPPSPACE, PNP, PNC, Вот почему я исключенPиз списка выше. Так как я знаюNPCoNP spearates P а также NPТакже я включил вопрос отдельно. Так у вас есть цитата, где конкретно говоритсяNPCoNP?
T ....

Ответы:

12

Есть (по крайней мере) две области, где существующие барьеры мало что могут сказать:

Нижние границы ACC Нет никакого известного барьера для доказательства того, что TC0 не находится в (неоднородном) ACC - кроме возможности того, что разделение может быть ложным. Неясно, должен ли барьер Natural Proofs применяться к ACC. Вопрос сводится к следующему: следует ли ожидать появления в ACC псевдослучайных функций?

LOGSPACE против NP Как указывает Fortnow , существующие механизмы оракула для ограниченных в пространстве вычислений, по-видимому, не представляют реального барьера для LOGSPACE против NP. Насколько мне известно, известные модели оракула, которые приводят к коллапсу LOGSPACE и NP, также разрушают Чередующийся LOGSPACE (то есть, P) и Чередующийся POLYTIME (то есть, PSPACE), следовательно, эти оракулы обрабатывают чередующиеся вычислительные модели несовместимо с реальностью (поскольку LOGSPACE не равен в пространство).

Райан Уильямс
источник
6

Результат Разборова и Рудича в их статье о естественных доказательствах является довольно общим. Это не ограниченоP против NP,

Мне лично нравится ясность объяснения в недавней книге Стасиса Юкны « Сложность булевой функции: достижения и границы »:

Определение 18.30. ФункцияG:{0,1}l{0,1}n с l<n называется (s,ϵ)безопасный псевдослучайный генератор, если для любой схемы C размера s на n переменные,

|Pr[C(y)=1]Pr[C(G(x))=1]|<ϵ,
где y выбран равномерно наугад в {0,1}n, а также x в {0,1}l,

Определение 18.31. Позволятьf:0,1n0,1быть булевой функцией. Мы говорим, чтоf является (s,ϵ)-трудно, если для какой-либо цепи C размера s,

|Pr[C(x)=f(x)]12|<ϵ,
где x выбран равномерно наугад в {0,1}n,

Генератор псевдослучайных функций является булевой функцией f(x,y):{0,1}n+n2{0,1}, Установивyслучайные переменные, мы получаем его случайную подфункцию fy(x)=f(x,y), Позволятьh:{0,1}n{0,1}быть действительно случайной булевой функцией. Генераторf(x,y) защищен от Γ-приступает, если для каждой цепи C в Γ,

|Pr[C(fy)=1]Pr[C(h)=1]|<2n2.

Γестественное доказательство против Λ это свойство Φ:Bn0,1удовлетворяющих следующим трем условиям:
1. Полезность противΛ : Φ(f)=1 подразумевает fΛ,
2. Большая:Φ(f)=1 как минимум 2O(n) доля всего 22n функции fBn,
3. Конструктивность:ΦΓто есть, когда рассматривается как логическая функция в N=2n переменные, свойство Φ сам принадлежит к классу Γ,

Теорема 18.35. Если класс сложностиΛ содержит генератор псевдослучайных функций, который защищен от Γ-атак, то нет Γестественное доказательство против Λ,

Вопрос в следующем: 1. Верим ли мы в существование таких сложных функций? 2. Насколько конструктивными / большими мы ожидаем, что свойства в возможных в настоящее время доказательствах разделения будут?

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

Помимо работ Райана Уильямса за последние несколько лет, он упомянул две статьи:

  1. Тимоти Чоу , « Почти естественное доказательство », 2008, в котором говорится, что если мы немного ослабим величие, то есть естественные свойства, которые могли бы отделитьNP от P,

  2. Эрик Аллендер и Михал Куки , « Усиление нижних границ с помощью самовосстанавливаемости », 2008, в котором говорится, что отделитьNC1 от TC0 нам нужно только доказать слегка суперлинейные нижние оценки на размер TC0схемы вычисления задачи оценки булевой формулы. Существование естественных доказательств такой нижней оценки не представляется необоснованным.

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

Можно извлечь непростые функции диагонализации из косвенных результатов диагонализации, такие как нижние границы пространства-времени для SAT.

Кава
источник
«.... это безопасно против Γ-атак» - это то же самое, что OWF в P против NP как когда мы сравниваем говорят L против NL или NP против coNP или PH против PSpace?
T ....
Итак, вы подразумеваете, что цепи в NP, CoNP, PH а также PSPACE все не могут сломать OWF в классе, против которого мы их рассматриваем (например, в NP Vs CoNPсхемы в CoNP не могут сломать OWF в NP)? Правильно ли это толкование? Один вопрос для завершения цикла. Имеет лиLесть PNG?
T ....
1
Γопределяет количество конструктивности, которую вы хотите из доказательства, а не из более крупного класса.
Каве
@JAS, кстати, если бы я был тобой, я бы не принял ответ так быстро, ты мог бы получить лучшие ответы.
Каве
о хорошо .... я не уверен, что лучше дать, кроме того, что в книге, хотя.
T ....