Dlaczego tak niewielu naturalnych kandydatów na pośredni status NP?

29

Twierdzenie Ladnera dobrze wie, że jeśli , wówczas istnieje nieskończenie wiele pośrednich ( ). Istnieją również naturalni kandydaci do tego statusu, tacy jak Graph Isomorphism i wiele innych, patrz Problemy między P i NPC . Niemniej jednak ogromna większość w tłumie znanych jest znana z lub . Tylko niewielka część z nich pozostaje kandydatem do . Innymi słowy, jeśli losowo wybierzemy naturalnyN P N P I natural N P P N P C N P I N P N P IPNPNPNPInatural NPPNPCNPINP-problem wśród znanych, mamy bardzo małą szansę na wybranie kandydata . Czy jest jakieś wytłumaczenie tego zjawiska?NPI

Mógłbym wymyślić 3 możliwe wyjaśnienia, bardziej filozoficzne:

  1. Powodem posiadania tak małej frakcji naturalnych kandydatów jest to, że ostatecznie okaże się pusty. Wiem, że oznacza to , więc jest bardzo mało prawdopodobne. Niemniej jednak nadal można argumentować (choć nie jestem jednym z nich), że rzadkość naturalnych problemów jest obserwacją empiryczną, która wydaje się w rzeczywistości wspierać , w przeciwieństwie do większości innych obserwacji.N P I P = N P N P I P = N PNPINPIP=NPNPIP=NP

  2. Małe „natural- ” reprezentuje rodzaj ostrego przejścia fazowego między łatwymi i trudnymi problemami. Najwyraźniej znaczące, naturalne problemy algorytmiczne zachowują się w taki sposób, że są albo łatwe, albo trudne, przejście jest wąskie (ale nadal istnieje).NPI

  3. Argument z 2 może być doprowadzony do skrajności: w końcu wszystkie problemy w „natural- ” zostaną wprowadzone do , a jednak , więc . Oznaczałoby to, że wszystkie pozostałe problemy wPN P C PN P N P IN P INPIPNPCPNPNPINPIsą „nienaturalne” (wymyślone, bez sensu życia). Interpretacją tego może być to, że naturalne problemy są albo łatwe, albo trudne; przejście jest tylko logiczną konstrukcją, bez znaczenia „fizycznego”. Jest to nieco podobne do przypadku liczb niewymiernych, które są całkowicie logiczne, ale nie powstają jako zmierzona wartość jakiejkolwiek wielkości fizycznej. Jako takie nie pochodzą one z rzeczywistości fizycznej, są raczej w „logicznym zamknięciu” tej rzeczywistości.

Które wyjaśnienie najbardziej ci odpowiada, czy możesz zasugerować inne?

Andras Farago
źródło
13
Długość przekątnej kwadratu 1 cm x 1 cm jest liczbą nieracjonalną ...
Joshua Grochow
4
Interesujące może być również to, że w teorii miary ograniczonej do zasobów zbiór zbiorów NP-zupełnych ma miarę p 0. Innymi słowy, zbiory p-losowe w NP nie są NP-kompletne. Rzeczywiście, dotyczy to każdego stopnia wielomianowego wielokrotnego czasu. (Miara zbioru wszystkich zbiorów NP jest pytaniem otwartym: jeśli jest niezerowa lub niemożliwa do zmierzenia, to .)PNP
Joshua Grochow
7
odpowiedź dotyczy głównie tego, jakie problemy uważamy za „naturalne”, co jest raczej filozoficznym pytaniem. nie jest też całkiem jasne, czy przesłanka tego pytania jest taka: wiele problemów związanych z kryptografią ma pośrednią złożoność. wreszcie to, co mówisz o liczbach nieracjonalnych, jest absurdalne.
Sasho Nikolov

Odpowiedzi:

26

Jak zauważyli inni, dyskusyjne jest, w jakim stopniu rzecz, którą próbujesz wyjaśnić, jest prawdziwa. Można argumentować, że w latach 60. i 70. informatycy teoretyczni byli po prostu bardziej zainteresowani rodzajem problemów, które okazały się albo w P, albo w NP-zupełnym. Dzisiaj, ze względu na wzrost złożoności - kryptografii teoretycznej, obliczeń kwantowych, sieci itp. - a także prostego faktu, że kompletność NP stała się tak dobrze zrozumiała - coraz bardziej interesujemy się rodzaje problemów, które okazują się być pośrednimi NP.

Mimo to można zapytać: w takim stopniu, w jakim rzecz jest prawdziwa - to znaczy w takim stopniu, że tak wiele naturalnych problemów z wyszukiwaniem i optymalizacją „przyciąga” albo być NP-zupełnym, albo też w P --- w tym zakresie , dlaczego jest to prawda? Tutaj myślę, że można uzyskać wiele intuicji, patrząc na wcześniejsze zjawisko od obliczalności: że tak wiele naturalnych modeli obliczeń „zatrzaskuje się” aż do ukończenia Turinga. W takim przypadku powiem, że wyjaśnienie jest takie, że gdy masz kilka podstawowych składników --- pamięć do odczytu / zapisu, pętle, warunki warunkowe itp. - trudno jest tego uniknąćmożliwość symulowania maszyny Turinga, a tym samym ukończenie Turinga. W podobny sposób, gdy problem wyszukiwania lub optymalizacji składa się z kilku podstawowych elementów --- co najważniejsze, możliwość konstruowania „gadżetów” naśladujących bramki logiczne, takie jak AND, OR i NOT --- trudno jest uniknąć do kodowania SAT i dlatego jest NP-kompletny.

Tak jak lubię o tym myśleć, problemy takie jak SAT wywierają potężne „przyciąganie grawitacyjne” na wszystkie inne problemy obliczeniowe w ich sąsiedztwie, powodując, że chcą „złapać” się na ukończenie NP również. Tak więc normalnie nie wymaga nawet specjalnego wyjaśnienia, gdy kolejny problem ulega temu pociągnięciu! Bardziej uderzające i wymagające wyjaśnienia jest to, że (pozornie) trudny problem NP ma jakąś właściwość, która pozwala mu oprzeć się grawitacyjnemu oddziaływaniu SAT. Następnie chcemy wiedzieć: co to za właściwość? Dlaczego nie możesz zagrać w zwykłą sztuczkę NP-zupełności dotyczącą tego problemu, polegającą na tworzeniu gadżetów kodujących logiczne bramki logiczne? W ostatniej odpowiedzi na CS.SE stworzyłem listę typowych odpowiedzi na to pytanie, ale (jak już zauważył inny komentator) istnieją inne możliwe odpowiedzi, które przeoczyłem.

Scott Aaronson
źródło
Również ostatnia część ma znaczenie dla pytania Scotta cstheory.stackexchange.com/questions/19256/…
András Salamon
17

Wiele naturalnych problemów można wyrazić jako problemy związane z ograniczeniami, a dla CSP istnieją twierdzenia o dychotomii.

Joshua Grochow
źródło
9

Po prostu żart: po zastanowieniu się nad „przyciąganiem grawitacyjnym SAT” w miłej odpowiedzi Scotta Aaronsona, przyszła mi do głowy inna metafora: kanapka 3-SAT 2-SAT !

wprowadź opis zdjęcia tutaj



... ale nie wiem, czy kanapkę można napełnić naturalnymi składnikami (jednak zauważyłem, że można ją wypełnić niektórymi - Sos SAT [1], jeśli hipoteza czasu wykładniczego jest prawdziwa) :-D(2+(logn)kn2)

Innym wynikiem w [1] jest to, że nie można go wypełnić .(2+1/n2ϵ),0<ϵ<2

[1] Yunlei Zhao, Xiaotie Deng, CH Lee, Hong Zhu, -SAT i jego właściwości(2+f(n)) , Discrete Applied Mathematics, tom 136, wydanie 1, 30 stycznia 2004 r., Strony 3-11, ISSN 0166 -218X.

Marzio De Biasi
źródło
3
(2+ε)
(2+f(n))(2+1/n2ϵ),0<ϵ<2(2+ϵ)
3
(2+f(n))
1
@MarzioDeBiasi powinieneś rozważyć dodanie tych dwóch odniesień bezpośrednio do swojej odpowiedzi (tam, gdzie można je przeszukiwać) zamiast ukrywania ich w komentarzach.
Artem Kaznatcheev
8

NPNPNPNPPNP

NPNPNP

NPFPTW[1]

Referencje :

1- M. Grohe. Złożoność problemów homomorfizmu i satysfakcji z ograniczeń widziane z drugiej strony. Journal of the ACM, 54 (1), art. 1, 2007

2 - Peter Jonsson, Victor Lagerkvist i Gustav Nordh. Dmuchanie dziur w różnych aspektach problemów obliczeniowych, z zastosowaniami do spełnienia ograniczenia. W materiałach z 19. Międzynarodowej Konferencji nt. Zasad i Praktyki Programowania Ograniczeń (CP-2013). 2013.

Mohammad Al-Turkistany
źródło
1
dlaczego te problemy CSP nie mieszczą się w domysłach dychotomii?
Sasho Nikolov
1
Czy ograniczenie szerokości, tak jak w przypadku Grohe, jest rzeczywiście naturalne? (Pytanie nie jest retoryczne - szczerze mówiąc nie wiem.) Moim zdaniem konstrukcje Johnsson-Lagerkvsit-Nordh wydają się tylko nieco bardziej naturalne niż konstrukcje Ladnera . Myślę, że punkt w pierwszym akapicie jest doskonały.
Joshua Grochow
@JoshuaGrochow Obawiam się, że jest to dyskusyjne, ponieważ nie ma formalnego pojęcia, co oznacza naturalny .
Mohammad Al-Turkistany
@SashoNikolov Czy masz na myśli przypuszczenie dychotomii Feder i Vardi?
Mohammad Al-Turkistany
1
A__B
7

Oto bajka o strukturze Złotowłosa problemów pośrednich NP. (Ostrzeżenie: ta historia może być użytecznym błędem do generowania i testowania potencjalnych hipotez, ale nie ma być naukowo rygorystyczna. Opiera się na jednej części wykładniczej hipotezy czasowej, odrobinie magii złożoności Kołmogorowa, niektórych fragmentów zapożyczonych z teorii SAT rozwiązywanie, a heurystyczna trichotomia Terence'a Tao w przypadku problemów. Spożywać na własne ryzyko, jak w przypadku wszystkich wymyślonych mikstur dotyczących matematyki).

Jeśli prawie wszystkie wystąpienia problemu w NP mają wysoce ustrukturyzowaną strukturę, wówczas problem dotyczy w rzeczywistości P. W ten sposób prawie wszystkie wystąpienia zawierają dużo nadmiarowości, a algorytm wielomianowy dla problemu jest sposobem na wykluczenie nadmiarowości. Można sobie nawet wyobrazić, że każdy problem w P można uzyskać, biorąc jakiś problem w EXP i dodając pewną ustrukturyzowaną redundancję, poprzez jakąś formę wypełniania (niekoniecznie zwykłego rodzaju). Gdyby tak było, to algorytm czasu wielomianowego mógłby być postrzegany jako skuteczny sposób na cofnięcie tego wypełnienia.

Jeśli jest wystarczająco dużo instancji, które nie są ustrukturyzowane, tworząc „rdzeń twardości”, problem jest NP-zupełny.

Jeśli jednak ten „rdzeń twardości” jest zbyt rzadki, wówczas ma tylko miejsce na reprezentację części SAT, więc problem występuje w P lub NP-pośrednim. (Ten argument jest istotą twierdzenia Ladnera). Aby użyć analogii Scotta, „rdzeń twardości” wywiera grawitacyjny wpływ na problem, w kierunku jego zupełności NP. Instancje w „rdzeniu twardości” nie zawierają zbyt dużej nadmiarowości, a jedynym realistycznym algorytmem, który działa dla wszystkich tych instancji, jest wyszukiwanie metodą brute force (oczywiście, jeśli jest ich tylko wiele, to działa również wyszukiwanie tabel).

Z tej perspektywy problemy NP-pośrednie powinny być rzadkie w praktyce, ponieważ wymagają one równowagi Goldilocks między instancjami, które są ustrukturyzowane i nieustrukturyzowane. Instancje powinny mieć wystarczającą redundancję, aby były częściowo podatne na algorytm, ale powinno wystarczyć rdzeń twardości, aby problem nie występował w P.


Można opowiedzieć jeszcze prostszą (i zabawną, ale także potencjalnie bardziej mylącą) historię opartą na łamigłówkach. Z kilkoma ograniczeniami można zmusić do przeprowadzenia wielu poszukiwań, na przykład NxN Sudoku jest NP-kompletny. Rozważmy teraz prośbę o rozwiązanie wielu małych łamigłówek za jednym razem, za jednym razem (np. Wiele Sudokusów 9x9). Wymagany czas będzie mniej więcej liniowy w liczbie puzzli w każdym przypadku, a ten problem jest następnie w P. W przypadku problemów pośrednich można pomyśleć, że każde wystąpienie jest dużą (ale niezbyt dużą) liczbą Sudokusów w dużej (ale niezbyt duże) siatki. Powodem, dla którego nie obserwujemy wielu takich problemów, jest to, że pozowanie i rozwiązywanie ich byłyby ponure!

András Salamon
źródło
1
LCLknk+kCLPL) wysunięto hipotezę, że języki w NP z wystarczająco gęstymi rdzeniami muszą być NP-kompletne.
Joshua Grochow
1
Odniesienia Joshua wymienione: Lynch: dx.doi.org/10.1145/321892.321895 i Orponen-Schöning: dx.doi.org/10.1016/S0019-9958(86)80024-9 zobaczyć również Orponen-Ko-SCHöNING-Watanabe: dx. doi.org/10.1145/174644.174648
András Salamon
2

NPINPINP

nlognNPI NPxQxQNPIP

NPINPNPINPC

NPIP

Andras Farago
źródło
3
W[1]
xQxO(log|x|)
W przypadku 3-COLORING, jaka jest zmniejszona wersja problemu?
András Salamon,
1
nlogn
2
Nie jest to różnica między czarno-białym „byciem kliką” a „byciem 3-kolorowym”. Różnica między pierwotnym problemem polega na tym, że: 1) wykres ma podgraph z pewną właściwością o danym rozmiarze (np. CLIQUE) vs. 2) wykres ma właściwość. W przypadku (1) zmiana rozmiaru na log jest naturalna, b / c rozmiar podgrafu był już częścią pytania. Kiedy wykonujesz sztuczkę do (2), dodajesz rozmiar podgrafu jako nową część problemu.
Joshua Grochow