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$

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?

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 C O N P -Complete.$\mathsf{NP}$$\mathsf{coNP}$

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

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

Można przyjąć dowodu, że nie jest rzadki -Complete języka chyba, że P = c o N P , która jest równoważna P = N P (od P 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 P = N P, to każdy nietrywialny język jest N P- 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 c O N P -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}$

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

Wspomniany projekt zawiera pełny dowód.