Czy „Gdzie są naprawdę trudne problemy”? Jakie są aktualne pomysły na ten temat?

Uważam ten artykuł za bardzo interesujący. Podsumowując: omawia, dlaczego w praktyce rzadko znajduje się najgorszy przypadek problemu NP-zupełnego. Idea tego artykułu polega na tym, że przypadki są zwykle bardzo niedostatecznie lub bardzo przeciążone, a oba są stosunkowo łatwe do rozwiązania. Następnie proponuje dla kilku problemów miarę „ograniczenia”. Wydaje się, że problemy te mają „przejście fazowe” od 0 prawdopodobieństwa rozwiązania do 100% prawdopodobieństwa. Następnie hipoteza:

1. Że wszystkie problemy związane z NP (a nawet wszystkie problemy z NP) mają miarę „powściągliwości”.
2. Że dla każdego problemu NP-zupełnego można utworzyć wykres prawdopodobieństwa rozwiązania istniejącego w funkcji „ograniczenia”. Co więcej, wykres ten będzie zawierał przejście fazowe, w którym to prawdopodobieństwo szybko i dramatycznie wzrasta.
3. Najgorsze przykłady problemów związanych z NP-zupełnością dotyczą przejścia fazowego.
4. Fakt, czy problem polega na tym przejściu fazowym, pozostaje niezmienny w przypadku transformacji jednego problemu pełnego NP.

Ten artykuł został opublikowany w 1991 roku. Moje pytanie brzmi: czy w ciągu ostatnich 25 lat były jakieś badania uzupełniające te pomysły? A jeśli tak, to co o nich myśli obecny główny nurt? Czy uznano je za prawidłowe, niepoprawne, nieistotne?

Oto przybliżone podsumowanie statusu na podstawie prezentacji wygłoszonej przez Vardiego podczas warsztatów na temat teorii modeli skończonych i algorytmicznych (2012):

Zaobserwowano, że trudne przypadki leżą w przejściu fazowym od regionu niedostatecznie do nadmiernie ograniczonego. Podstawowa hipoteza jest taka, że ​​istnieje silny związek między przejściami fazowymi a złożonością obliczeniową problemów NP.

Achlioptas – Coja-Oghlan stwierdził, że w zadowalającym regionie występuje gęstość, w której przestrzeń rozwiązania rozbija się wykładniczo na wiele małych klastrów. Vinay Deolalikar oparł swoją słynną próbę udowodnienia na założeniu, że rozbicie oznacza twardość obliczeniową. Dowód Deolalikara został obalony przez fakt, że XOR-SAT jest w i rozpada się. Dlatego rozbicia nie można użyć do udowodnienia twardości obliczeniowej.$P \ne NP$$P$

Obecne myślenie głównego nurtu wydaje się (jak stwierdził Vardi), że przejścia fazowe nie są nieodłącznie związane ze złożonością obliczeniową.

Wreszcie, oto artykuł opublikowany w Nature, który bada związek między przejściami fazowymi a twardością obliczeniową K-SAT.

Tak, było dużo pracy od czasu publikacji Cheesemana, Kanefsky'ego i Taylora w 1991 roku.

Przeszukanie recenzji przejść fazowych problemów NP-Complete da wiele wyników. Jedną z takich recenzji jest Hartmann i Weigt [1]. Aby zapoznać się z wprowadzeniem na wyższy poziom, zobacz artykuły amerykańskiego naukowca Briana Hayesa [2] [3].

Artykuł Cheesemena, Kanefsky'ego i Taylora z 1991 roku jest niefortunnym przypadkiem informatyków, którzy nie zwracają uwagi na literaturę matematyczną. W artykule Cheesemana, Kanefsky'ego i Taylora zidentyfikowali Cykl Hamiltona jako przejście fazowe ze wzrostem kosztów wyszukiwania w pobliżu progu krytycznego. Zastosowany przez nich model wykresu losowego był losowym wykresem Erdosa-Renyi (ustalone prawdopodobieństwo krawędzi lub równorzędny rozkład stopni Gaussa). Ten przypadek został dobrze zbadany przed publikacją Cheesemana i wszystkich z 1991 roku ze znanymi prawie pewnymi wielomianowymi algorytmami czasowymi dla tej klasy grafu, nawet przy progu krytycznym lub blisko niego. Dobrym przykładem jest „Losowe wykresy” Bollobasa [4]. Pierwotny dowód, który, jak sądzę, został przedstawiony przez Angliun i Valiant [5], a kolejne ulepszenia Bollobas, Fenner i Frieze [6]. Po Cheesemanie,

Przejście fazowe dla cykli Hamiltona w losowych losowych wykresach Erdosa-Renyi istnieje w tym sensie, że istnieje szybkie przejście prawdopodobieństwa znalezienia rozwiązania, ale nie przekłada się to na wzrost „wewnętrznej” złożoności znalezienia cykli Hamiltona. Prawie pewne są algorytmy wielomianowe do znajdowania cykli hamiltonowskich w losowych grafach Erdosa-Renyi, nawet przy krytycznym przejściu, zarówno w teorii, jak i w praktyce.

Propagacja badania [8] odniosła duży sukces w znalezieniu zadowalających przypadków losowej 3-SAT bardzo blisko progu krytycznego. Moja obecna wiedza jest nieco zardzewiała, więc nie jestem pewien, czy nastąpił duży postęp w znalezieniu „wydajnych” algorytmów dla niezadowalających przypadków w pobliżu progu krytycznego. O ile mi wiadomo, 3-SAT jest jednym z przypadków, w których „łatwo” go rozwiązać, jeśli jest zadowalający i zbliżony do progu krytycznego, ale nieznany (lub trudny?) W przypadku niezadowalającego blisko progu krytycznego.

Moja wiedza jest już trochę przestarzała, ale kiedy po raz ostatni zagłębiłem się w ten temat, wyróżniało się kilka rzeczy:

• Cykl Hamiltona jest „łatwy” dla losowych wykresów Erdosa-Renyi. Gdzie są trudne problemy?
• Podział liczbowy powinien być możliwy do rozwiązania, gdy bardzo daleko w prawie pewnym prawdopodobieństwie 0 lub 1 regionie, ale nie istnieją wydajne algorytmy (o ile mi wiadomo) dla nawet umiarkowanych rozmiarów wystąpień (1000 liczb po 500 bitów każdy, o ile mi wiadomo, jest całkowicie trudny do rozwiązania z najnowocześniejsze algorytmy). [9] [10]
• 3-SAT jest „łatwy” w przypadku zadowalających wystąpień w pobliżu progu krytycznego, nawet w przypadku dużych rozmiarów wystąpień (miliony zmiennych), ale trudny w przypadku niezadowalających wystąpień w pobliżu progu krytycznego.

Waham się tutaj, ponieważ nie opublikowałem żadnych recenzowanych artykułów, ale napisałem swoją pracę magisterskąw temacie. Główną ideą jest to, że możliwą klasą zespołów losowych (cykle hamiltonowskie, problem podziału liczbowego itp.), Które są „wewnętrznie twarde”, są te, które mają właściwość „niezmienności skali”. Rozkłady stabilne podatkowo są jednym z bardziej naturalnych rozkładów o tej jakości, z ogonami prawa mocy, i można wybierać losowe wystąpienia z zestawów NP-Complete, które w jakiś sposób zawierają rozkład stabilny podatkowo. Dałem trochę słabych dowodów na to, że można znaleźć wewnętrznie trudne instancje cyklu Hamiltonianowskiego, jeśli losowe wykresy zostaną wybrane z rozkładem stopnia stabilnego wg Levy'ego zamiast rozkładu normalnego (tj. Erdos-Renyi). Jeśli nic więcej, będzie to przynajmniej punkt wyjścia do przeglądu literatury.

[1] AK Hartmann i M. Weigt. Przejścia fazowe w problemach optymalizacji kombinatorycznej: podstawy, algorytmy i mechanika statystyczna. Wiley-VCH, 2005.

[2] B. Hayes. Najłatwiejszy trudny problem. American Scientist, 90 (2), 2002.

[3] B. Hayes. Na progu American Scientist, 91 (1), 2003.

[4] B. Bollobás. Losowe wykresy, wydanie drugie. Cambridge University Press, Nowy Jork, 2001.

[5] D. Angluin i LG Valiant. Szybkie algorytmy probabilistyczne dla obwodów Hamiltona i dopasowań. J. Computer, Syst. Sci., 18: 155–193, 1979.

[6] B. Bollobás, TI Fenner i AM Frieze. Algorytm znajdowania ścieżek i cykli Hamiltona na losowych wykresach. Combinatorica, 7: 327–341, 1987.

[7] B. Vandegriend i J. Culberson. Przejście fazowe Gn, m nie jest trudne dla problemu cyklu Hamiltona. J. of AI Research, 9: 219–245, 1998.

[8] A. Braunstein, M. Mézard i R. Zecchina. Propagacja ankiety: algorytm satysfakcji. Struktury losowe i algorytmy, 27: 201–226, 2005.

[9] I. Gent i T. Walsh. Analiza heurystyki dla podziału liczb. Inteligencja obliczeniowa, 14: 430–451, 1998.

[10] CP Schnorr i M. Euchner. Redukcja podstawy kraty: Ulepszone praktyczne algorytmy i rozwiązywanie problemów sum częściowych. W Proceedings of Fundamentals of Computation Theory '91, L. Budach, red., Lecture Notes in Computer Science, tom 529, strony 68–85, 1991.

25 lat nauki i gdzie są obecne pomysły:

+++ pomysł 1:

Z mojego doświadczenia w rozwiązywaniu problemów z zadowalaniem odkryłem w praktyce, że dodanie prawidłowej klauzuli k do formuły, którą próbujemy rozwiązać, jest podobne do decydowania o zmiennej (nk) qbf.

Wydaje się, że jest to podejście do pokazania, że ​​obecne metody rozwiązywania problemów w sieciach satelitarnych są trudne!

+++ pomysł 2:

Innym pomysłem jest to, że problem AllQBF jest prawdziwym problemem w hierarchii boolowskiej. Problem AllQBF polega na: Wytworzenie logicznego wyrażenia Q, które decyduje o wszystkich 2 ^ n qbfach formuły R. AllQBF jest łatwe, gdy oryginalna formuła R jest monotoniczna lub 2-cnf.

Wszystkie QBF wydają się prawdopodobną drogą do pokazania QBF to Exp, ponieważ Q jest często wykładniczy, więc ocena przypisania Q (kwantyfikacja oryginalnej formuły R) jest wykładnicza. Tak więc droga do udowodnienia NP to Exp zawiera przynajmniej kilka cegieł.

+++ idea 3: Zwykłe k-cnfs

Przy okazji, we wszystkich badaniach przemiany fazowej pominięto Regularne k-cnfs, gdzie liczba wystąpień zmiennej (w obu kierunkach) jest stała, podobnie jak w przypadku regularnych wykresów ... Regularne k-cnfs stają się znacznie trudniejsze niż model standardowy, ponieważ wszystkie zmienne wyglądają identycznie pod względem ograniczeń na nich.

Dwadzieścia pięć lat temu, tuż po przeczytaniu cheesemana, skupiłem się na stopniowym kolorowaniu grafów, ponieważ wszystkie zmienne wyglądają tak samo. Wykorzystam więc ten przywilej odpowiedzi i przedstawiam dwadzieścia pięć lat wyników na regularnych wykresach!

+++ pomysł 4: Złote punkty za badania porównawcze satysfakcji

Dość intensywnie badałem zabarwienie C grafów D regularnych N wierzchołków. Poniższa tabela podsumowuje wyniki Golden Point dla regularnego kolorowania wykresów.

Dla wysokiego prawdopodobieństwa N losowych wystąpień było zadowalających. Dla Very High N ^ 2 były zadowalające. W przypadku Super High losowe przypadki N ^ 3 były zadowalające.

Punkty złotego kolorowania o wysokim prawdopodobieństwie (1 - 1 / N) to:

C3D5N180 C4D6N18 C4D7N35 C4D8N60 C4D9N180? C5D10N25 C5D11N42 C5D12N72

Punkty barwienia o bardzo wysokim prawdopodobieństwie (1 - 1 / (N ^ 2)) to:

C3D5N230? C4D6N18 C4D7N36 C4D8N68 C4D9N ??? C5D10N32 C5D11N50 C5D12N78

Punkty złotego zabarwienia o bardzo wysokim prawdopodobieństwie (1 - 1 / (N ^ 3)) to:

C3D5N ??? C4D6N22 C4D7N58 C4D8N72? C4D9N ??? C5D10N38 C5D11N58 C5D12N ??

Wpis C4D9 oznacza cztery kolory wykresów dziewiątego stopnia. To najtrudniejsze losowe 4cnfs, jakie spotkałem w ciągu 25 lat rozwiązywania problemów. Niedawno pokolorowałem wykres dziewiątego stopnia 172 wierzchołek po dziesięciu dniach procesora.

+++ Idea 5: C5D16N ???? Przypuszcza się, że Golden Point istnieje.

Dzięki, Daniel Pehoushek