„Prawie łatwe” problemy z kompletnym NP

Powiedzmy, że język jest blisko P, jeśli istnieje algorytm wielomianowy, który poprawnie decyduje o na prawie wszystkich wejściach. $L$ $L$

Innymi słowy, istnieje P , tak że zanika, co oznacza Oznacza to również, że przy jednolitym losowym danych wejściowych algorytm czasu policyjnego dla da poprawną odpowiedź dla z prawdopodobieństwem zbliżającym się do 1. Dlatego sensowne jest zobaczenie prawie łatwo. $A\in$ $L\Delta A$

lim_{n \to \infty} \frac{| (L Δ A) \cap {0, 1}^{n} |}{2^{n}} = 0.

$\lim_{n\rightarrow\infty} \frac{|(L\Delta A) \cap \{0,1\}^n|}{2^n}=0.$

A

$A$

L

$L$

L

$L$

Zauważ, że $L\Delta A$ nie musi być rzadka. Na przykład, jeśli ma ciągi $2^{n/2}$ $n$ bit, to nadal zanika (w tempie wykładniczym), ponieważ $2^{n/2}/2^n=2^{-n/2}$ .

Zgodnie z powyższą definicją nie jest trudno (sztucznie) konstruować problemy kompletne z NP , które są P -zamknięte. Na przykład, niech $L$ będzie dowolnym językiem uzupełniającym NP i zdefiniuj $L^2=\{xx\,|\, x\in L\}$ . Wtedy $L^2$ zachowuje kompletność NP , ale ma co najwyżej $2^{n/2}$ $n$ -bitowe wystąpienia tak. Dlatego trywialny algorytm, który odpowiada „nie” na każdym wejściu, poprawnie decyduje o $L^2$ na prawie wszystkich wejściach; będzie błądził tylko na $\leq 1-2^{-n/2}$ części $n$ bitowych danych wejściowych.

Z drugiej strony, byłoby bardzo zaskakujące, gdyby wszystkie problemy związane z NP były blisko P -gęstości. Oznaczałoby to, że w pewnym sensie wszystkie problemy z NP są prawie łatwe. To motywuje pytanie:

Zakładając, że P $\neq$ NP , jakie są niektóre naturalne problemy z NP -zupełnością , które nie są blisko P -gęstością?

cc.complexity-theory ds.algorithms complexity-classes np-complete Andras Farago
źródło

Od Heuristica nie jest wykluczone, że nie jest nawet nie-koniecznie-naturalny problem dla którego P ≠ NP jest znany sugerować, że problem nie jest prawie w P.

Uważam, że problemy z korespondencją pocztową są dobrym problemem dla kandydatów. Jest to trudne nawet w przypadku równomiernie losowych przypadków, a zatem jest trudne w przeciętnym przypadku.

Mohammad Al-Turkistany

FYI: Twój wybór nomenklatury, choć naturalny, jest sprzeczny z niektórymi istniejącymi nomenklaturami: klasa Prawie-P składa się z tych języków L, że ma miarę 1. Możesz być także zainteresowany wiedz, że rzadka wersja twojej definicji została już użyta i ma powiązania z kilkoma innymi pomysłami, patrz P-close . Biorąc pod uwagę definicję P-close, być może dobrą nazwą dla twojej koncepcji jest P-gęstość-zamknięcie lub P-zamknięcie-wystarczająco :).

{A : L \in P^{A}}

$\{A : L \in P^A\}$

Joshua Grochow

Z drugiej strony problem decyzyjny dotyczący „ zabarwienia wykresu ” jest prawdopodobnie kandydatem na taki problem.

$\;$

Nie jestem przekonany, że to właściwa definicja. Jeśli zagęszczenie zniknie, wówczas jest to „prawie łatwe” za pomocą dowolnego trywialnego języka , bez względu na to, jak trudne jest w rzeczywistości. Jednak trudno jest pokazywać naturalne, twarde języki w stosunku do alfabetu z gęstością, która nie znika, po prostu z powodu kodowania. Czy przecięcie nie powinno dotyczyć poprawnych danych wejściowych o rozmiarze (więc jest to problem z obietnicą), a nie wszystkich ciągów? W przeciwnym razie wymaga to przede wszystkim odpowiedzi na pytanie: czy istnieje logiczne kodowanie jakiegoś języka NP-twardego o gęstości, która nie znika?

L

$L$

A

$A$

{0, 1}

$\{0,1\}$

n

$n$

András Salamon,

Zbadałem, czy w teorii złożoności istnieje ogólnie przyjęta hipoteza, która implikuje, że musi istnieć język kompletny z NP , którego nie można zaakceptować w czasie wielomianowym dla prawie wszystkich danych wejściowych (jak zdefiniowano w pytaniu).

Co ciekawe, najbardziej „standardowe” hipotezy nie sugerują tego. Oznacza to, że nie wydaje się (chyba że coś przeoczyłem) z P NP , P BPP , NP coNP , E NE , EXP NEXP , NP PSPACE , NP EXP , NP P / poly, PH się nie zwija itp. $\neq$ $=$ $\neq$ $\neq$ $\neq$ $\neq$ $\neq$ $\not\subseteq$

Z drugiej strony znalazłem jedną, nieco mniej standardową hipotezę, która implikuje istnienie poszukiwanego problemu NP- zupełnego, choć nie naturalnego. W teorii miary ograniczonej do zasobów podstawową hipotezą jest to, że NP nie ma pomiaru zero, oznaczonego przez NP . Nieformalnie oznacza to, że języki NP w E nie tworzą pomijalnego podzbioru. Aby uzyskać szczegółowe informacje, zobacz ankietę tutaj . W tej teorii dowodzą one między innymi, że NP implikuje istnienie P $p$ $\mu_p($ $)\neq 0$ $\mu_p($ $)\neq 0$ -bi-odporny język w NP . Język jest P -Bi-odporny, jeżeli ani , ani jego dopełnieniem jest nieskończony podzbiór w P . Taki język w zdecydowany sposób spełnia nasze wymagania. $L$ $L$

Jednak nadal nie jest jasne, czy istnieje przykład, który stanowi naturalny problem.

Andras Farago
źródło

Bi-odporność jest również znacznie silniejsza niż twój stan i jest związana z bardziej powszechnym użyciem „prawie wszystkich” w teorii złożoności strukturalnej, a mianowicie „dla wszystkich, ale ostatecznie wielu” ...

Joshua Grochow

@JoshuaGrochow Zgadzam się, ale wydaje się, że w pewnym sensie odporność na P-bi oznacza zbyt silną trudność. Wydaje się, że nie występuje wśród naturalnych problemów NP-zupełnych. Zaskakujące jest dla mnie, że najwyraźniej nie ma rezultatu, który zapewniłby jedynie warunki do istnienia „słabo prawie wszędzie” trudnego do opanowania języka NP. Przez „słabo prawie wszędzie” rozumiem, że warunek „wszyscy prawie skończeni” zostaje zastąpiony przez „wszyscy prawie znikający”. Może to lepiej odnosić się do tego, co naprawdę spotyka się w praktyce.

Andras Farago,

Czy wiadomo, że NP jest mierzalny p?

@RickyDemer O ile mi wiadomo, nie wiadomo, czy NP można zmierzyć p.

Andras Farago,

„Prawie łatwe” problemy z kompletnym NP

Odpowiedzi: