Czy istnieje język NP-complete, który zawiera dokładnie połowę n-bitowych instancji?

Czy istnieje (najlepiej naturalny) NP-pełny język $L\subseteq \{0,1\}^*$ , taki, że dla każdego $n\geq 1$

| L \cap {0, 1}^{n} | = 2^{n - 1}

$|L\cap \{0,1\}^n|=2^{n-1}$ trzyma? Innymi słowy,

L

$L$ zawiera dokładnie połowę wszystkich

n

$n$ bitowych instancji.

cc.complexity-theory np np-complete

— Andras Farago
źródło

Byłoby bardzo zaskakujące, gdyby nie było, ale myślenie o tym przez kilka minut nie mogło znaleźć konstrukcji.

— Kaveh

FWIW jest taki

który jest NP-trudny i w NP / POLY ...

L

$L$

— Neal Young

Dla dwuskładnikowego binarnego kodowania

wzorów CNF,

zadowalające

niezadowalający

powinien działać.

e

$e$

{e (φ) 1 | φ

$\{e(\varphi)1\ |\ \varphi$

} \cup {e (φ) 0 | φ

$\} \cup \{e(\varphi)0\ |\ \varphi$

}

$\}$

— Klaus Draeger

@KlausDraeger Niezadowolenie nie jest własnością NP, chyba że NP = co-NP.

— Andras Farago,

Czy istnieje jakaś wyrocznia

, która nie istnieje

z tą właściwością?

O

$O$

L \in {N P - C o m p l e t e}^{O}

$\mathcal{L}\in {\bf NP-Complete}^O$

— Erfan Khaniki

Odpowiedzi:

Zadałem to pytanie kilka lat temu i Boaz Barak odpowiedział na nie pozytywnie .

Stwierdzenie jest równoważne z istnieniem kompletnego języka NP gdzie jest obliczalny w czasie wielomianowym. $L$ $|L_n|$

Rozważmy formuły logiczne i SAT. Używając dopełniania i nieznacznie modyfikując kodowanie formuł, możemy upewnić się, że i mają tę samą długość. $\varphi$ $\lnot \varphi$

Niech być kodowanie $\langle\ \rangle$

dla wszystkich formuł i dla wszystkich przypisań prawdy , . $\varphi$ $\tau \in \{0,1\}^{|\varphi|}$ $|\langle\varphi\rangle| = |\langle\varphi, \tau\rangle|$
jest obliczalny w czasie wielomianowym. $|\langle\varphi\rangle| \mapsto |\varphi|$
liczba wzorów o zakodowanej długości jest obliczalna w czasie wielomianowym. $n$

Rozważmy

L := {⟨ φ ⟩ ∣ φ \in S A T} \cup {⟨ φ, τ ⟩ ∣ τ ⊨ φ and \exists σ < τ σ ⊨ φ}

$L := \{\langle\varphi\rangle \mid \varphi \in \mathsf{SAT} \} \cup \{\langle \varphi, \tau \rangle \mid \tau \vDash \varphi \text{ and } \exists \sigma<\tau\ \sigma\vDash\varphi \}$

Łatwo zauważyć, że jest NP-kompletny. $L$

Jeśli , liczba przypisań prawdy spełniających jest równa liczbie zadowalających przypisań prawdy . Dodając , sumuje się do liczby zadowalających przypisań prawdy dla . $\varphi \in \mathsf{SAT}$

τ ⊨ φ and \exists σ < τ σ ⊨ φ

$\tau \vDash \varphi \text{ and } \exists \sigma<\tau\ \sigma\vDash\varphi$

- 1

$- 1$

φ

$\varphi$

φ

$\varphi$

Istnieją zadania prawdy. Każdy albo spełnia albo (i nie oba). Dla każdej formuły , rozważmy struny , , i dla $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$ . Dokładniez tych łańcuchy są w . Oznacza to, że liczba łańcuchów o długości w jest liczbą preparatów długości zakodowanego pomnożone przezktóry jest obliczalny w czasie wielomianowym. $\tau \in \{0,1\}^{|\varphi|}$ $2^{|\varphi|}$ $2^{|\varphi|+1}+2$ $L$ $n$ $L$ $\varphi$ $n$ $2^{|\varphi|}$

— Ryan O'Donnell
źródło

Nawet jeśli jest to pożądane rozwiązanie, jest to odpowiedź wyłącznie z linkiem.

— user2943160,

dla jasności, nie ma nic specjalnego w SAT, działałoby to z dowolnym predykatem weryfikatora dla problemu NP-zupełnego.

— Kaveh

@Kaveh, czy nie używasz tutaj szczególnej właściwości SAT, że wystąpienia występują w parach

tak, że każdy świadek

jest świadkiem dokładnie jednego z dwóch w parze? Jak byś to zrobił np. Dla 3-COLOR?

ϕ

$\phi$

\neg ϕ

$\lnot \phi$

τ

$\tau$

— Neal Young,

@Neal, niech V (x, y) będzie weryfikatorem problemu NP-zupełnego. Rozważmy W (x, b, y): = V (x, y) = b. Nadal jest NP-kompletny i każdy y jest świadkiem dla x, 0 lub x, 1. Jednak nie tak miły jak SAT.

— Kaveh,

@Kaveh, np. Z SAT sugerujesz

Ale to jest w P, a jeśli spróbujesz to naprawić, biorąc związek, powiedzmy,

, związek

A = {(ϕ, b, τ) : (τ satisfies ϕ) \leftrightarrow b = 1} ?

$A = \{(\phi, b, \tau) : (\tau \mbox{ satisfies } \phi) \leftrightarrow b=1\}?$

B = {(ϕ, b) : τ \in S A T \leftrightarrow b = 1}

$B = \{(\phi, b) : \tau \in SAT \leftrightarrow b = 1\}$

A \cup B

$A\cup B$ is both NP-hard and co-NP-hard (so likely not in NP). EDIT: Oh, I see, you mean to take the union of

A

$A$ with, say,

C = {(ϕ, b) : \exists τ . [(τ satisfies ϕ) \leftrightarrow b = 1]}

$C=\{(\phi, b) : \exists \tau.~[(\tau \mbox{ satisfies } \phi) \leftrightarrow b=1]\}$ ...

— Neal Young

Here's a suggestion of why it might be difficult to come up with an example of such, though I agree with Kaveh's comment that it would be surprising if it didn't exist. [Not an answer, but too long for a comment.]

Suppose that someone, say me, comes up with such a language $L$ . A natural way for me to prove that $L^{=n} := |L \cap \{0,1\}^n| = 2^{n-1}$ is to explicitly build a bijection between $L \cap \{0,1\}^n$ and $\{0,1\}^n \backslash L$ . Since I personally am not able to decide instances of $\mathsf{NP}$ -hard problems, most "simple" bijections that I will come up with will have the form " $f\colon \{0,1\}^* \to \{0,1\}^*$ is a length-preserving bijection, and $x \in L$ if and only if $f(x) \notin L$ ." Furthermore, I'm likely to come up with such an $f$ that is computable in polynomial time. But then $\mathsf{NP} = \mathsf{coNP}$ , for $f$ is a reduction from an $\mathsf{NP}$ -complete set to a $\mathsf{coNP}$ -complete one.

Of course, this objection can be gotten around by "simply" having the bijection be harder to compute than that. If your bijection takes exponential time - say it and its inverse might both be $\mathsf{EXP}$ -hard - then I think you're pretty safe. But if it only takes, say, quasi-polynomial time, then note that you still get the consequence $\mathsf{coNP} \subseteq \mathsf{NTIME}(2^{(\log n)^{O(1)}}) =: \mathsf{NQP}$ , from which I believe it follows by a simple induction with padding argument that $\mathsf{PH} \subseteq \mathsf{NQP}$ . Now, if you believe the preceding containment is simply false, then no such quasi-poly-time computable bijection can save you. But even if you believe it might be true, then by coming up with such a bijection you would prove $\mathsf{PH} \subseteq \mathsf{NQP}$ , which seems to be beyond current knowledge...

The objection can also be gotten around by simply not having such a bijection, but then it seems harder to see how to prove that $L$ has the desired property in the first place... And in fact, even if your proof isn't a bijection, you'd need it to be the case that no such easily computable bijection even exists.

Of course, this is also the type of thing where someone will come along with an example and we'll easily see how it gets around this objection, but I just wanted to throw this out there to say how anything with a simple enough bijection can't work (unless widely held beliefs are false).

(Related question: is there an oracle relative to which there is no such $L$ ?)

— Joshua Grochow
źródło