Насколько я понимаю, доказательство того, что P = NP или P ≠ NP, должно быть нерелятивизируемым (как в оракулах теории рекурсии).
Практически все доказательства кажутся релятивизируемыми.
Какие хорошие примеры , не являющиеся Релятивизуемых доказательств, из тех , что Р = NP / P ≠ NP доказательству было бы нужно быть, что не являются тривиальными или надуманными?
(Я не теоретик рекурсии, поэтому прошу прощения за отсутствие цитат.)
[РЕДАКТИРОВАТЬ: лучше сообщение Mathoverflow ]
Ответы:
Как Стивен примечаний, канонический пример . Этот коллапс не релятивизируется, в том смысле, что существует оракул A , подчиняющийся I P A ≠ P S P A C E AIP=PSPACE A IPA≠PSPACEA . Интуиция, почему известное доказательство этого результата избегает барьера релятивизации, состоит в том, что он использует арифметизацию (Йонатан упомянул об этом в комментарии): интерактивный протокол для PSPACE - неполная задача TQBF задается путем рассмотрения расширения количественной булевой формулы до полинома низкой степени над достаточно большим полем. Если нам дать релятивизированную булеву формулу (с вратами оракула), такого расширения не существует.
Из-за Ааронсона и Вигдерсона происходит уточнение барьера релятивизации - алгебрирования . В общем, метод арифметизации недостаточен, чтобы обойти барьер алгебраизации. Класс сложности включение algebrizes , если для любого оракула А и любого расширения ~ A от A до низкой степени многочленов над конечным полем, C A ⊆ D ~ A . Разделение C ⊄ D алгебрирует, если для всех A и всех расширений ˜ A , CC⊆D A A~ A CA⊆DA~ C⊄D A A~ . Ааронсон и Вигдерсон показывают, что I P = P S P A C E E алгебризирует, но многие другие результаты, включая N P ⊄ P , нет.CA~⊄DA IP=PSPACE NP⊄P
Недавний пример методики , которая не algebrize или релятивизировать является доказательством Райана Уильямса , что . Разделение не алгебрирует: существует оракул A и расширение ˜ A низкой степени, такое что N E X PNEXP⊄ACC A A~ . Интуитивно понятно, что доказательство позволяет избежать барьера в том, что оно основано на существовании более быстрого, чем тривиальный алгоритм выполнимости дляACCNEXPA~⊂ACCA ACC схемы, и алгоритм использует нерелятивизирующие и неалгебрирующие свойства таких схем. Райан отмечает в статье, что все известные более быстрые, чем тривиальные алгоритмы выполнимости ломаются при добавлении оракулов или алгебраических расширений оракулов.
Существует также интересный подход к пониманию релятивизации через логику. В старой рукописи Арора, Импальяццо и Вазирани определяют систему аксиом так, что релятивизирующие результаты являются именно теми, которые следуют из аксиом, а нерелятивизирующие результаты не зависят от системы. В работе Impagliazzo, Kabanets и Kolokolova что-то похожее для алгебризации вводится дополнительная аксиома к тем, которые определены Arora, Impagliazzo и Vazirani Они показывают, что большинство известных нерелятивизирующих результатов вытекают из их аксиом, в то время как P против NP, помимо прочего, не зависит от них.
Извиняюсь, если я что-то не так понял, я не совсем эксперт.
источник
Вот список нерелятивизируемых доказательств:
Теорема PCP
Обязательства, зависящие от экземпляра, подразумевают протокол с нулевым знанием:
эквивалентность между нулевым знанием и обязательствами
Не существует эффективного обфускатора виртуальных «черных ящиков» для общих схем:
эквивалентность нулевого знания и обязательств
Против незапутанных проверяющих, NEXP имеет минимально интерактивные системы проверки с двумя доказательствами: системы с
двумя испытаниями с одним доказательством: их сила и проблемы
Против возможных запутанных средств проверки NEXP имеет более интерактивные протоколы MIP:
интерактивное доказательство с несколькими доказательствами для звука NEXP против запутанных средств проверки
Джонатан Кац, продвинутые темы в криптографии, лекция 13
источник
Это хороший обзор области, проведенный ведущим экспертом, который суммирует / детализирует некоторые пункты других ответов до сих пор и имеет дополнительные примеры.
[1] Роль релятивизации в теории сложности Fortnow
источник