Снижение P против NP до SAT

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

Я намеренно пишу этот вопрос очень неформально. В отсутствие подробностей, это, возможно, указано немного неправильно. Пожалуйста, не стесняйтесь указывать на исправления в ваших ответах.

В следующей статье: «
Неприменимая криптография», Дэнни Долев, Синтия Дворк и Мони Наор, SIAM Rev. 45, 727 (2003), DOI: 10.1137 / S0036144503429856 ,
авторы пишут:

Предположим, что исследователь A получил доказательство того, что P ≠ NP, и хочет сообщить об этом факте профессору B. Предположим, что, чтобы защитить себя, A доказывает свою претензию на B с нулевым знанием ...

Существует несколько стандартных NP-полных задач, таких как выполнимость (SAT), Graph-Hamiltonicity и Graph-3-Colorability (G3C), для которых существуют доказательства с нулевым знанием. Стандартный способ доказательства любой NP-теоремы состоит в том, чтобы сначала свести ее к экземпляру вышеупомянутых NP-полных задач, а затем провести доказательство с нулевым знанием.

Этот вопрос относится к такому сокращению. Предположим, что P против NP рассчитывается любым из следующих способов:

• P = NP
• P ≠ NP
• P против NP не зависит от стандартной аксиоматической теории множеств.

Обозначим через σ доказательство. Тогда P против NP на NP языке (так как для этого существует краткое доказательство). Приведение от теоремы (скажем, P ≠ NP) к NP-полной задаче (скажем, SAT) не зависит от σ. Это:

There exists a formula ϕ which is satisfiable if and only if P ≠ NP.

Это далеко за пределами моего воображения! Кажется, что даже если нам дано доказательство σ, вряд ли мы сможем построить такую ​​формулу ϕ.

Может ли кто-нибудь пролить свет на это?

Кроме того, пусть L - NP-язык, на котором лежит P против NP . Язык состоит из бесконечного множества теорем, таких как P и NP , произвольных размеров.

Какой кандидат на Л?
Может ли L быть NP-завершенным?

Способ рассмотрения проверки математического утверждения (например, разрешения P против NP) как вопроса формы «является формулой… выполнимой» заключается в следующем:

Исправить некоторую систему аксиом. Для строки длины n, является ли строка доказательством для математического оператора в системе аксиом, это можно определить простым способом: строка должна состоять из предложений. Каждое предложение должно быть либо аксиомой, либо должно следовать из предыдущих предложений по одному из правил вывода.

Это не проблема определить булеву формулу, которая проверяет все это. Все, что вам нужно знать, это длина n доказательства!

P против NP находится в NP (поскольку существует краткое доказательство этого)

Это не имеет особого смысла для меня. NP - класс сложности для решения задач, которые имеют произвольно большие экземпляры, а P против NP не имеют их. Из того, что вы говорите позже:

пусть L - NP-язык, на котором лежит P против NP.

вместо этого вы можете иметь в виду, что P против NP является примером проблемы NP; но конечно это так! Это также пример бесконечного числа проблем P, DTIME (n) и т. Д. В частности, здесь есть два DTIME (1) кандидата на L, точно один из которых является правильным: всегда возвращаться true; или всегда возвращайся false.