Codzienne problemy z NP-zupełnymi problemami

Mark Dominus zebrał kilka przykładów redukcji czasu wielomianowego od różnych trudnych problemów NP do dopasowania „wyrażenia regularnego” . Wyobrażanie sobie weryfikacji w czasie wielomianowym nie jest ogromnym skokiem.

Jak zilustrujesz klasę NP-zupełną studentom lub przyjaciołom z innych dziedzin, którzy chcieli zrozumieć niedawne zamieszanie związane z pracą Deolalikara?

Mój ulubiony przykład do użycia z przyjaciółmi spoza CS to:

Abraham, A. Blum, Sandholm. Algorytmy rozliczeniowe dla rynków wymiany barterowej: umożliwienie ogólnopolskiej wymiany nerek. EC07.

Rynki wymiany nerki są zasadniczo ograniczoną formą ubezpieczenia rowerowego. Podoba mi się ten przykład, ponieważ a) łatwo jest wyjaśnić istotę (jeśli pominąć niektóre bardziej techniczne szczegóły) ib) jest to jeden z niewielu przypadków, w których wiem, gdzie lepsze algorytmy mogą dosłownie uratować życie!

Moim drugim ulubionym przykładem jest problem szpitali i mieszkańców (zwany także problemem przyjęć na studia). Każdy szpital zalicza wszystkich mieszkańców (kończących studia medyczne), a mieszkańcy szeregują szpitale. Każdy szpital ma określoną liczbę miejsc. Stamtąd jest to stabilny problem dopasowywania i można go rozwiązać w czasie wielomianowym.

Ale w rzeczywistości pary mogą wejść do systemu (tak, istnieje system ) razem, tak że system nie będzie na przykład dzielić małżeństw, które ubiegają się o miejsce zamieszkania. Dodanie par sprawia, że ​​problem NP jest kompletny. Oprócz tego, że jest łatwy do wyjaśnienia, ładnie pokazuje, w jaki sposób wprowadzenie połączeń dalekiego zasięgu może indukować kompletność NP.

Niektóre problemy „na co dzień”, które są trudne NP, odpowiednio sformułowane:

• Przypisywanie zajęć uniwersyteckich do przedziałów czasowych w celu zminimalizowania konfliktów planowania.

• Przypisywanie gości weselnych do miejsc, aby przyjaciele siedzieli przy tym samym stole, a wrogowie nie.

• Planujesz podróż, aby odwiedzić wszystkie miejsca turystyczne na liście, aby zminimalizować jazdę.

Problem podróżującego sprzedawcy jest najwyraźniej dostępny ... przynajmniej tam, gdzie jestem, wydaje się, że jest to najpopularniejszy problem wśród osób spoza CS. Znalazłem również następującą ilustrację Wierzchołka Pokrywy całkiem atrakcyjną, wprowadzoną przez mojego instruktora algorytmów:

Masz sieć dróg i chcesz się upewnić, że jeśli samochód utknie w paliwie, na co najmniej jednym końcu drogi znajduje się stacja benzynowa.

Jako urbanista chcesz zminimalizować koszty, budując możliwie najmniejszą liczbę stacji benzynowych. Zasadniczo jest to problem pokrycia wierzchołków, a ja odniosłem pewien sukces, wskazując, że chociaż nie spodziewasz się znaleźć optymalnej osłony wierzchołków w czasie wielomianowym, w czasie wielomianowym możesz znaleźć coś, co dzieli Cię tylko dwa razy, po prostu wybierając oba punkty końcowe o maksymalnym dopasowaniu (cóż, ten ostatni szczegół może zostać pominięty w zależności od stopnia zainteresowania odbiorców - zwłaszcza, że ​​algorytm MM nie jest dokładnie dwuliniowy).

Jako przykład „skoku złożoności” z niewielką zmianą charakteru problemu, uważam, że różnica między sprawdzaniem dwukolorowości i trójkolorowości stanowi dobry przykład. Przy całym rozgłosie wokół twierdzenia o czterech kolorach można również zauważyć, że sprawdzenie, czy mapę można odpowiednio pokolorować tylko trzema kolorami zamiast czterech, jest trudne, chociaż wiemy, że zawsze można ją pokolorować czterema kolorami. Sporo osób uważa to za dość zaskakujące.

Inną dość naturalną sytuacją jest problem odzyskiwania impasu w systemach operacyjnych. Jest to modelowane przez NP-kompletny problem zestawu wierzchołków sprzężenia zwrotnego - najmniejszej liczby wierzchołków, których usunięcie powoduje, że wykres jest acykliczny - i uważam, że jest to również niezwykły przykład (i wyjaśniono to dalej w tym artykule na Wikipedii).

Myślę, że parkowanie równoległe jest trudne NP.

W rzeczywistości bardziej ogólny problem ze znalezieniem najkrótszej ścieżki z ograniczoną krzywizną, która przenosi obiekt wielokątny z jego początkowej pozycji do ostatecznej pozycji w środowisku wielokąta, jest trudny do przeprowadzenia. Dowód można znaleźć tutaj - http://portal.acm.org/citation.cfm?id=298976

Plecak jest dość łatwy do uchwycenia, szczególnie dla każdego, kto miał do czynienia z małą walizką. Dobry przykład, jeśli zna programowanie dynamiczne.

Kolejną zabawną (praktycznie identyczną) jest suma cząstkowa, ponieważ ma również przyjemną fizyczną interpretację: wyobraź sobie, że liczby są odległościami równych mas punktowych na idealnej (bezmasowej) linijce, z punktem podparcia na początku. Suma częściowa mówi: czy istnieje niepusty podzbiór taki, że linijka pozostanie zrównoważona? (tj. taki, że środek ciężkości jest punktem podparcia dla linijki?)

W obu przypadkach intuicyjne wydaje się, że naiwne strategie mogą wymuszać uciekanie się do sprawdzania wszystkich podzbiorów.

Jeśli mają więcej tła, fajnie jest rozwiązywać problemy, usuwając ograniczenia. Na przykład, zaczynając od problemu maksymalnego przepływu, przekształcając go w program liniowy i czyniąc go programem całkowitym. (Świetny jest oczywiście MAX-CUT, ponieważ dla osób z większym doświadczeniem możesz również przywołać UGC; Dotykam trochę tego w odpowiedzi MO https://mathoverflow.net/questions/33036/is-quadratic-programming -still-np-hard-if-you-have-bounds-and-a-feasible-point / 33048 # 33048. ) Są też fajne rzeczy, takie jak pozornie podobne problemy, które mają znacznie różną złożoność (ścieżka Eulera (krawędzi) jest liniowa czas ścieżka Hamiltonian (wierzchołek) jest NP-kompletna).

Konstrukcja krzyżówki jest NP-Complete: Biorąc pod uwagę zestaw odpowiedzi, spróbuj dopasować je do siatki.

Stworzyłem stronę internetową Tagxedo, http://www.tagxedo.com , generator chmury słów, który dopasowuje słowa do kształtu (wielkości według częstotliwości). Wyniki są bardzo ładne, ale łatwo udowodnić, że problem jest trudny do przeprowadzenia (problem pakowania).

Co ciekawe, wiele problemów trudnych dla NP ma „łatwe” przybliżenie. W wielu przypadkach Tagxedo wykonuje prawie idealną robotę. Prowadzi to do interesującej dyskusji na temat praktycznej implikacji P vs NP i tematu przybliżenia.

Jeden z moich przyjaciół spędził sabatyczny rok oglądając mecz baseballowy na każdym dużym stadionie ligowym w Ameryce Północnej. Bez latania. (Nie do końca mu się udało; w tym roku budowano trzy stadiony).

Ze względu na sukces takich firm jak Uber i Lyft wiele osób ma bardzo łatwo dostępne bezpośrednie doświadczenie z problemami NP-zupełnymi.

Biorąc pod uwagę zbiór kierowców i listę osób, które chcą być odbierane o różnych porach, jaki jest najbardziej efektywny przydział pasażerów dla kierowców?

Ten problem (po odpowiednim sformułowaniu) to NPC i wyobrażam sobie, że ludzie w pewnym momencie zastanawiali się, w jaki sposób Uber decyduje się sparować kierowców i pasażerów.

Zwykle używam SAT jako przykładu. Mówię coś w stylu: „wszelkiego rodzaju problemy, które pojawiają się cały czas, można przepisać jako szukanie prawdziwego przypisania do wielkiej formuły logicznej. Pytanie P vs NP dotyczy tego, czy istnieje zasadniczo łatwiejszy sposób rozwiązania tej formuły logicznej niż tylko wypróbowanie wszystkich możliwości. Jak dotąd nikt nie był w stanie ani znaleźć sposobu, ani udowodnić, że nie ma łatwego wyjścia ".

Np-kompletny problem, taki jak Sudoku (na nxn sqaure), jest jak uniwersalne narzędzie, które pozwala nam skutecznie rozwiązywać wszystkie problemy, które mają skutecznie weryfikowalne rozwiązania. Jedynym wymaganiem jest posiadanie wydajnej metody rozwiązywania Sudoku.

$NP$

$n$$p_j$$m$$NP$$p_j$$k$$NP$-kompletne w tej sytuacji. Zauważ, że nie muszą to być bloki, pod warunkiem, że zakładamy, że nie mogą się przewrócić. Mogą to być stosy papierów, skrzyń lub talerzy.

Mam nadzieję że to pomoże!

Kapryśnie dostępnym przykładem jest krótka prezentacja Marka Dominusa (patrz powiązany post na blogu ) zatytułowana „Mój ulubiony problem NP-Complete”, w której zdjęcie poniżej stanowi dokładny zarys dokładnej okładki 3 zestawów .

Tytuły z serii wideo obejmują

• Taniec, muzyka i książki
• Dłonie, uszy i stopy
• Obudź się z Elmo (o spaniu, ubieraniu się i myciu zębów)
• Ludzie w twoim sąsiedztwie (o strażakach, ratownikach i pielęgniarkach)

Oczywistym celem było, aby każdy film zawierał trzy odcinki o wspólnym temacie, zaczerpnięte z puli tematów interesujących małe dzieci.

Dziwna kaczka w serii była filmem na temat „kwiatów, bananów i… włosów”.

Zwłaszcza, gdy przyjrzymy się później problemowi plecakowemu, ten problem NP-zupełny może być dobrym rozwiązaniem:

Zgadywanie liczb, w którym możesz zgadywać tylko pojedyncze liczby, dopóki nie uzyskasz właściwego wyniku.