Eine dichte NP-vollständige Sprache impliziert P = NP

Wir sagen , dass die Sprache ist dicht , wenn es ein Polynom existiert , so dass für alleMit anderen Worten, für eine gegebene Länge existieren nur polynomisch viele Wörter der Länge , die nicht in $J \subseteq \Sigma^{*}$ $p$

| J^{c} \cap Σ^{n} | \leq p (n)

$|J^c \cap \Sigma^n| \leq p(n)$

n \in N .

$n \in \mathbb{N}.$

n

$n$

n

$n$

J .

$J.$

Bei dem Problem, das ich gerade studiere, muss Folgendes gezeigt werden

Wenn es eine dichte vollständige Sprache gibt, dann ist $NP$ $P = NP$

Was der Text vorschlägt, ist, die Polynomreduktion auf - und dann einen Algorithmus zu konstruieren, der versucht, die gegebene Formel zu erfüllen und gleichzeitig Elemente in erzeugen $3$ $SAT$ $CNF$ $J^c.$

Was ich mich wundere, ist

Gibt es einen direkteren Beweis? Ist dieser Begriff allgemeiner bekannt?

complexity-theory time-complexity np-complete satisfiability Jernej
quelle

Es gibt eine verwandte Vorstellung von spärlichen Sprachen, in der die Bedingung genau umgekehrt ist: .

| J \cap Σ^{n} | \leq p (n)

$|J \cap \Sigma^n| \leq p(n)$

Yuval Filmus

Schauen Sie sich Mahaneys Satz an .

Pål GD

@ PålGD In eine Antwort verwandeln? (Angenommen, das Argument überträgt sich auf dichte Sprachen)

Yuval Filmus

Antworten:

Dies ist ein schönes Hausaufgabenproblem zu Mahaneys Theorem.

Beachten Sie, dass das Komplement einer "dichten" Sprache eine spärliche Sprache ist. Wenn eine Sprache -vollständig ist, ist ihre Ergänzung -vollständig. $\mathsf{NP}$ $\mathsf{coNP}$

Wenn es eine "dichte" -vollständige Sprache gibt, gibt es eine spärliche -vollständige Sprache. $\mathsf{NP}$ $\mathsf{coNP}$

Der Satz von Mahaney besagt, dass es keine spärliche -vollständige Sprache gibt, es sei denn, . $\mathsf{NP}$ $\mathsf{P}=\mathsf{NP}$

Wir können den Beweis übernehmen, dass es keine spärliche -vollständige Sprache gibt, es sei denn, entspricht (seit ist unter Ergänzungen geschlossen). $\mathsf{coNP}$ $\mathsf{P}=\mathsf{coNP}$ $\mathsf{P}=\mathsf{NP}$ $\mathsf{P}$

Zusammenfassend lautet die Antwort nein, es sei denn, . Beachten Sie, dass bei jede nichttriviale Sprache -vollständig ist. $\mathsf{P}=\mathsf{NP}$ $\mathsf{P}=\mathsf{NP}$ $\mathsf{NP}$

ps: Vielleicht möchten Sie Folgendes ausprobieren und dann Theorem : Es gibt eine spärliche -komplette Menge, wenn es eine spärliche -komplette Menge gibt. Ich bezweifle jedoch, dass ein Beweis für diese Aussage viel einfacher wäre als ein Beweis für Mahaneys Theorem. $\mathsf{NP}$ $\mathsf{coNP}$

Kaveh
quelle

$NP-Hard$ $P=NP$

Der erwähnte Entwurf enthält einen vollständigen Beweis.

Reza
quelle

Dies gibt nicht mehr als den Kommentar (der nicht einmal Ihnen gehört). Bitte erläutern Sie ausführlich, wie Sie diesen Beitrag richtig beantworten können.

Raphael

@ Raffael: Es ist eine richtige Antwort. Hast du den Link überprüft?

Tsuyoshi Ito

@TsuyoshiIto: Antworten, die nur aus einem Link bestehen, werden bei SE im Allgemeinen als schlecht angesehen. siehe hier .

Raphael

@Raphael: Die beantwortete Frage wurde bisher in der Literatur gelöst. Der Link enthält einen vollständigen Beweis (das sind 6 Seiten). Ich denke, wenn er mehr Fragen hat, könnten wir mit der Diskussion fortfahren.

Reza

@ Raffael: Blöd. Ein Link ist besser als nichts. Wenn Sie möchten, erarbeiten Sie die Antwort selbst, anstatt einen Benutzer für das Posten eines nützlichen Links zu beschuldigen.

Tsuyoshi Ito