Влияет ли естественное доказательство , релятивизация и алгебризация на разделение других классов сложности, таких как т. Д.?
Например, барьер естественных доказательств должен влиять на любое доказательство поскольку он будет отделять . Однако отношения между и , по-видимому, не имеют большого отношения к OWF по сравнению с отношением между и . Так влияют ли естественные доказательства на более сильное разделение ?
cc.complexity-theory
barriers
Т ....
источник
источник
Ответы:
Есть (по крайней мере) две области, где существующие барьеры мало что могут сказать:
Нижние границы ACC Нет никакого известного барьера для доказательства того, что TC0 не находится в (неоднородном) ACC - кроме возможности того, что разделение может быть ложным. Неясно, должен ли барьер Natural Proofs применяться к ACC. Вопрос сводится к следующему: следует ли ожидать появления в ACC псевдослучайных функций?
LOGSPACE против NP Как указывает Fortnow , существующие механизмы оракула для ограниченных в пространстве вычислений, по-видимому, не представляют реального барьера для LOGSPACE против NP. Насколько мне известно, известные модели оракула, которые приводят к коллапсу LOGSPACE и NP, также разрушают Чередующийся LOGSPACE (то есть, P) и Чередующийся POLYTIME (то есть, PSPACE), следовательно, эти оракулы обрабатывают чередующиеся вычислительные модели несовместимо с реальностью (поскольку LOGSPACE не равен в пространство).
источник
Результат Разборова и Рудича в их статье о естественных доказательствах является довольно общим. Это не ограниченоP против NP ,
Мне лично нравится ясность объяснения в недавней книге Стасиса Юкны « Сложность булевой функции: достижения и границы »:
Вопрос в следующем: 1. Верим ли мы в существование таких сложных функций? 2. Насколько конструктивными / большими мы ожидаем, что свойства в возможных в настоящее время доказательствах разделения будут?
С другой стороны, Разбаров упоминал в разных местах, что он лично рассматривает результат как руководство к тому, чего следует избегать, а не как существенное препятствие для доказательства нижних оценок.
Помимо работ Райана Уильямса за последние несколько лет, он упомянул две статьи:
Тимоти Чоу , « Почти естественное доказательство », 2008, в котором говорится, что если мы немного ослабим величие, то есть естественные свойства, которые могли бы отделитьNP от P ,
Эрик Аллендер и Михал Куки , « Усиление нижних границ с помощью самовосстанавливаемости », 2008, в котором говорится, что отделитьNC1 от TC0 нам нужно только доказать слегка суперлинейные нижние оценки на размер TC0 схемы вычисления задачи оценки булевой формулы. Существование естественных доказательств такой нижней оценки не представляется необоснованным.
Релятивизация и алгебраизация немного сложнее и зависят от того, как мы определяем релятивизацию для этих классов. Но, как правило, простая диагонализация (диагонализация, которая использует один и тот же контрпример для всех машин, вычисляющих одну и ту же функцию, т. Е. Контрольный пример зависит только от того, какие машины в меньших вычислениях, и не зависит от их кода и того, как они вычисляют. ) не может разделить эти классы.
Можно извлечь непростые функции диагонализации из косвенных результатов диагонализации, такие как нижние границы пространства-времени для SAT.
источник