Gęsty NP pełny język oznacza P = NP

Mówimy, że język jest gęsty, jeśli istnieje wielomian taki, że dla wszystkichInnymi słowy, dla dowolnej długości istnieje tylko wielomianowo wiele słów o długości , które nie są w $J \subseteq \Sigma^{*}$ $p$

| {jot}^{do} \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.$

Problem, który obecnie badam, wymaga przedstawienia następujących informacji

Jeśli istnieje gęsty język , wówczas $NP$ $P = NP$

Tekst sugeruje rozważenie redukcji wielomianu do - a następnie skonstruowanie algorytmu, który próbuje spełnić daną formułę jednocześnie generując elementy w $3$ $SAT$ $CNF$ $J^c.$

Zastanawiam się

Czy istnieje bardziej bezpośredni dowód? Czy to pojęcie jest znane w bardziej ogólnym kontekście?

— Jernej
źródło

Istnieje pokrewne pojęcie rzadkich języków, w których warunek jest odwrotny: .

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

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

— Yuval Filmus

Sprawdź twierdzenie Mahaneya .

— Pål GD

@ PålGD Zamieniasz się w odpowiedź? (zakładając, że spór zostanie przeniesiony do gęstych języków)

— Yuval Filmus

Odpowiedzi:

To niezły problem do odrobienia w domu o twierdzeniu Mahaneya.

Zauważ, że dopełnieniem „gęstego” języka jest rzadki język. Ponadto, jeżeli język -Complete jego dopełniacza -Complete. $\mathsf{NP}$ $\mathsf{coNP}$

Jeśli nie jest to „gęsty” -Complete język nie jest rzadki -Complete języka. $\mathsf{NP}$ $\mathsf{coNP}$

Twierdzenie Mahaney mówi nam, że nie ma rzadki -Complete język chyba . $\mathsf{NP}$ $\mathsf{P}=\mathsf{NP}$

Można przyjąć dowodu, że nie jest rzadki -Complete języka chyba, że , która jest równoważna (od jest zamknięty pod uzupełnieniami). $\mathsf{coNP}$ $\mathsf{P}=\mathsf{coNP}$ $\mathsf{P}=\mathsf{NP}$ $\mathsf{P}$

Podsumowując, odpowiedź brzmi nie, chyba że . Zauważ, że jeśli to każdy nietrywialny język jest kompletny. $\mathsf{P}=\mathsf{NP}$ $\mathsf{P}=\mathsf{NP}$ $\mathsf{NP}$

PS: Można spróbować następujących czynności i wykorzystać twierdzenie Mahaney za: jest rzadki -Complete zestaw IFF jest rzadki -Complete zestaw. Wątpię jednak, aby dowód na to stwierdzenie byłby znacznie łatwiejszy niż dowód na twierdzenie Mahaneya. $\mathsf{NP}$ $\mathsf{coNP}$

— Kaveh
źródło

Jak wspomniano powyżej zgodnie z twierdzeniem Mahaneya . Języki rzadkie i mogą być gęste nie , chyba że . $NP-Hard$ $P=NP$

Wspomniany projekt zawiera pełny dowód.

— Reza
źródło

To nie daje więcej niż komentarz (który nie jest nawet twój). Opracuj, aby poprawnie odpowiedzieć na ten post.

— Raphael

@Raphael: To poprawna odpowiedź. Czy sprawdziłeś link?

— Tsuyoshi Ito

@TsuyoshiIto: Odpowiedzi składające się tylko z linku są ogólnie uważane za złe w SE; patrz tutaj .

— Raphael

@Raphael: Pytanie, na które odpowiedziano, zostało wcześniej rozwiązane w literaturze. Link zawiera cały dowód (6 stron). Myślę, że gdyby miał więcej pytań, moglibyśmy kontynuować dyskusję.

— Reza

@Raphael: Silly. Link jest lepszy niż nic. Jeśli chcesz, opracuj odpowiedź samodzielnie, zamiast obwiniać użytkownika za opublikowanie przydatnego linku.

— Tsuyoshi Ito