Можно ли использовать результаты релятивизации для доказательства формально независимых предложений?

12

Можно ли продемонстрировать, что предложение должно быть формально независимым, основываясь на том факте, что оно нерелятивизирующее? Другими словами, есть ли в предложениях теории вычислимости / сложности примеры предложений, где можно продемонстрировать, что а) что все доказательства, которые решают вопрос о том, равны ли два класса, должны быть релятивизированы, и б) что нет релятивизирующих доказательств, которые можно использовать в таком разрешении?

Я думаю, что результаты, удовлетворяющие части b, будут легче получить. Другой способ задать этот вопрос: существовало ли когда-нибудь в теории вычислимости или сложности предложение, в котором можно продемонстрировать, что равенство или неравенство должны устанавливаться с помощью (и только с помощью) методов релятивизации? Пример этого был бы мне интересен.

Благодарность; ответ на любой вариант этого вопроса был бы очень интересным для меня.

-Philip

Филип Уайт
источник

Ответы:

18

Не существует «естественных» вопросов теории сложности, которые были бы доказаны независимо от действительно мощных формальных систем, таких как теория множеств ZF или арифметика Пеано. (Конечно, такой вопрос можно построить искусственно, играя в игры с предложениями Гёделя.)

С другой стороны, да, вы можете интерпретировать утверждение, что предложение S релятивизируется как означающее, что S может быть доказано из некоторого ограниченного набора аксиом (в основном, «аксиом Кобхэма», которые характеризуют замыкание при сокращениях за полиномиальное время). И наоборот, существование оракулов, делающих S истинным или ложным, эквивалентно тому, что S не зависит от этих конкретных аксиом. Вот статья об этом, которую читали Арора, Импальяццо и Вазирани.

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

Скотт Ааронсон
источник
4
Я думаю, что Импальяццо-Кабанец-Колоколова распространил Арора-Импальяццо-Вазирани на арифметику в STOC 2009: dx.doi.org/10.1145/1536414.1536509
Джошуа