Есть ли NP-полный язык, который содержит ровно половину n-битных экземпляров?

Есть ли (желательно натурального) NP-полный язык $L\subseteq \{0,1\}^*$ , такое , что для любого имеет место ? Другими словами, содержит ровно половину всех битных экземпляров.$n\geq 1$

Я задал этот вопрос несколько лет назад, и Вооз Барак положительно ответил на него .

Это утверждение эквивалентно существованию NP-полного языка где | L n | вычисляется за полиномиальное время.$L$$|L_n|$

Рассмотрим булевы формулы и SAT. Использование отступов и слегка изменив кодировку формул мы можем убедиться , что и ¬ φ имеют одинаковую длину.$\varphi$$\lnot \varphi$

Пусть быть кодировка,$\langle\ \rangle$

• для всех формул и для любого задания истинности τ ∈ { 0 , 1 } | φ | , | ⟨ Ф ⟩ | = | ⟨ Ф , т ⟩ | ,$\varphi$$\tau \in \{0,1\}^{|\varphi|}$$|\langle\varphi\rangle| = |\langle\varphi, \tau\rangle|$
• вычисляется за полиномиальное время.$|\langle\varphi\rangle| \mapsto |\varphi|$
• число формул с закодированной длиной вычисляется за полиномиальное время.$n$

Рассмотрим

Легко видеть, что является NP-полной.$L$

Если , то число истинных назначений, удовлетворяющих τ ⊨ φ  и  ∃ σ < τ σ ⊨ φ , равно числу удовлетворяющих истинных назначений - 1 . Добавление φ само по себе добавляет к числу удовлетворяющих истинных назначений для φ .$\varphi \in \mathsf{SAT}$

Есть Истина назначения. Каждый τ либо удовлетворяет φ, либо ¬ φ (а не оба). Для каждой формулы ф , рассмотрим 2 ( 2 | ф | + 1 ) строки ⟨ φ ⟩ , ⟨ ¬ φ ⟩ , ⟨ φ , т ⟩ и ⟨ ¬ φ , т ⟩ для т ∈ { 0 $2^{|\varphi|}$$\tau$$\varphi$$\lnot \varphi$$\varphi$$2(2^{|\varphi|}+1)$$\langle\varphi\rangle$$\langle\lnot \varphi\rangle$$\langle\varphi, \tau\rangle$$\langle \lnot\varphi, \tau\rangle$, Именно 2 | φ | из этих 2 | φ | + 1 + 2 строки находятся в L . Это означает, что количество строк длины n в L - это число формул φ кодированной длины n, умноженное на 2 | φ | который полиномиального времени вычислим.$\tau \in \{0,1\}^{|\varphi|}$$2^{|\varphi|}$$2^{|\varphi|+1}+2$$L$$n$$L$$\varphi$$n$$2^{|\varphi|}$

Вот предложение о том, почему может быть трудно привести пример такого рода, хотя я согласен с комментарием Каве, что было бы удивительно, если бы его не было. [Не ответ, но слишком долго для комментария.]

Предположу , что кто - то, скажем , меня, приходит с таким языком . Для меня это естественный способ доказать, что L = n : = | L ∩ { 0 , 1 } n | = 2 п - 1 является явно построить взаимно однозначное соответствие между L ∩ { 0 , 1 } п и { 0 , 1 } п ∖ л . Так как я лично не могу решать случаи Н $L$$L^{=n} := |L \cap \{0,1\}^n| = 2^{n-1}$$L \cap \{0,1\}^n$$\{0,1\}^n \backslash L$$\mathsf{NP}$В трудных задачах большинство «простых» биекций, которые я придумаю, будут иметь вид « - биекция, сохраняющая длину, и x ∈ L тогда и только тогда, когда f ( x ) ∉ L. " Кроме того, я, вероятно, придумаю такое f , которое вычисляется за полиномиальное время. Но тогда N P = c o N P , так как f - это сокращение от N $f\colon \{0,1\}^* \to \{0,1\}^*$$x \in L$$f(x) \notin L$$f$$\mathsf{NP} = \mathsf{coNP}$$f$$\mathsf{NP}$-полный набор в -полный.$\mathsf{coNP}$

Конечно, это возражение можно обойти, просто «сделав», что вычисление биекции будет сложнее, чем это. Если ваша биекция занимает экспоненциальное время - скажем, и ее обратное значение может быть -hard - тогда, я думаю, вы достаточно безопасны. Но если это займет, скажем, квазиполиномиальное время, то обратите внимание, что вы все равно получите следствие c o N P ⊆ N T I M E ( 2 ( log n ) O ( 1 ) ) = : N Q P , из которого Я полагаю, что это следует из простой индукции с аргументом заполнения, который$\mathsf{EXP}$$\mathsf{coNP} \subseteq \mathsf{NTIME}(2^{(\log n)^{O(1)}}) =: \mathsf{NQP}$ . Теперь, если вы полагаете, что предыдущее ограничение просто ложно, то никакая такая квазиполисременная вычисляемая биекция не сможет вас спасти. Но даже если вы верите, что это может быть правдой, то, придумав такую ​​биекцию, вы докажете P H ⊆ N Q P , что, по-видимому, выходит за рамки современных знаний ...$\mathsf{PH} \subseteq \mathsf{NQP}$$\mathsf{PH} \subseteq \mathsf{NQP}$

Возражение также можно обойти, просто не имея такой биекции, но тогда кажется сложнее увидеть, как доказать, что обладает желаемым свойством в первую очередь ... И на самом деле, даже если ваше доказательство не является биекция, вам нужно, чтобы такой легко вычислимой биекции даже не существовало.$L$

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

(Смежный вопрос: есть ли оракул, относительно которого нет такого ?)$L$