Czy redukcje powinny nas bardziej lub mniej optymistycznie podchodzić do rozwiązania problemu?

Wydaje mi się, że większość teoretyków złożoności ogólnie uważa następującą zasadę filozoficzną:

Jeśli nie możemy wymyślić skuteczny algorytm dla problemu i możemy zmniejszyć problemu A do problemu B , wtedy prawdopodobnie nie jest skuteczny algorytm dla problemu B , albo.$A$$A$$B$$B$

Dlatego, na przykład, gdy nowy problem zostanie udowodnione, NP-complete po prostu złożyć ją jako „zbyt trudne”, a nie coraz podekscytowani nowym podejściu problemem ( ) może wreszcie pokazać, że P = N P .$B$$P = NP$

Rozmawiałem o tym z innym studentem z innej dziedziny naukowej. Uważała ten pomysł za niezwykle sprzeczny z intuicją. Jej analogia:

Jesteś odkrywcą i szukasz pomostu między kontynentami Ameryki Północnej i Azji. Przez wiele miesięcy próbowałeś i nie udało Ci się znaleźć mostu lądowego z kontynentu Stanów Zjednoczonych do Azji. Następnie odkrywasz, że kontynentalne Stany Zjednoczone są połączone lądem z obszarem Alaski. Zdajesz sobie sprawę, że most lądowy z Alaski do Azji oznaczałby most lądowy z lądu Stanów Zjednoczonych do Azji, co do którego na pewno nie istnieje. Więc nie trać czasu na eksplorację w pobliżu Alaski; po prostu idź do domu.

$A \to B$$B$$A$

Myślę, że to bardzo dobre pytanie. Aby odpowiedzieć na to pytanie, musimy zdać sobie sprawę, że:

• nie wszystkie redukcje są takie same,
• aby czuć się optymistycznie, musimy nauczyć się czegoś naprawdę pomocnego.

$A \to B$

1. Nauczyliśmy się czegoś pomocnego na temat problemu A (i nic na temat problemu B).
2. Nauczyliśmy się czegoś zniechęcającego na temat problemu B (i nic na temat problemu A).

Dokładniej te dwa przypadki można scharakteryzować następująco:

1. Odkryliśmy, że problem A ma ukrytą strukturę, która umożliwia zaprojektowanie nowego, sprytnego algorytmu rozwiązywania problemu A. Musimy tylko wiedzieć, jak rozwiązać problem B.

2. Zrozumieliśmy, że w niektórych szczególnych przypadkach problem B to po prostu problem A w przebraniu. Widzimy teraz, że każdy algorytm rozwiązywania problemu B musi poprawnie rozwiązać przynajmniej te specjalne przypadki; a rozwiązanie tych specjalnych przypadków jest zasadniczo równoznaczne z rozwiązaniem problemu A. Wracamy do punktu wyjścia: aby zrobić postęp w przypadku problemu B, musimy najpierw poczynić pewne postępy w zakresie problemu A.

Redukcje typu 1 są powszechne w kontekście pozytywnych wyników i są to z pewnością dobre powody do optymizmu.

Jeśli jednak weźmiesz pod uwagę obniżenia twardości, które napotykamy w kontekście np. Prób twardości NP, prawie zawsze są typu 2.

Zauważ, że nawet jeśli nie wiesz nic o złożoności obliczeniowej problemu A lub problemu B, możesz jednak stwierdzić, czy Twoja redukcja jest typu 1 czy typu 2. Dlatego nie musimy wierzyć, np. P ≠ NP, aby ustal, czy powinniśmy czuć się optymistycznie czy pesymistycznie. Możemy zobaczyć, czego się nauczyliśmy dzięki redukcji.

W analogii brakuje tego pojęcia względnych odległości. Zastąpmy Alaskę w naszej analogii do księżyca:

Jesteś odkrywcą i szukasz pomostu między kontynentami Ameryki Północnej i Azji. Przez wiele miesięcy próbowałeś i nie udało Ci się znaleźć mostu lądowego z kontynentu Stanów Zjednoczonych do Azji. Następnie odkrywasz, że kontynentalne Stany Zjednoczone są połączone lądem z Księżycem. Jesteś już pewien, że księżyc jest daleko od Azji, więc możesz być pewien, że Ameryka Północna jest również bardzo daleko od Azji z powodu nierówności trójkąta.

Nie jest prawdą, że zawsze traktujemy twierdzenia o redukcji jako stwierdzenia twardości. Na przykład w algorytmach często redukujemy problem do LP i SDP, aby je rozwiązać. Nie są one interpretowane jako wyniki twardości, ale wyniki algorytmiczne. Jednak chociaż są to ograniczenia techniczne, często nie nazywamy ich takimi. To, co rozumiemy przez redukcję, to zwykle redukcja do jakiegoś (NP-) trudnego problemu.

$A$$B$$A$$B$$B$$A$$A$$A$$B$$B$. Większość badaczy uważa za bardziej prawdopodobne, że P nie jest równe NP, a nawet przypuszcza, że ​​SAT wymaga czasu wykładniczego. Innymi słowy, uważa się, że SAT jest bardzo trudny. Jeśli zaakceptujesz te przypuszczenia, całkowicie uzasadnione jest przyjrzenie się redukcjom świadczącym o uniwersalności problemu NP, ponieważ problem jest trudny. (Dlaczego badacze uważają, że P nie równa się NP, jest bardziej prawdopodobne, to inny problem, na blogach teoretycznych pojawiło się kilka postów na ten temat.)

Częściowym powodem, dla którego zamieniamy dolną granicę na wyniki uniwersalności (tj. Jest redukcja z każdego problemu w klasie do problemu), jest nasz brak powodzenia w udowadnianiu dobrych ogólnych dolnych granic (jest to zgodne z obecnym stanem wiedzy że SAT można rozwiązać w liniowym deterministycznym czasie).

W rzeczywistości odkrycie Alaski miałoby odwrotny skutek, przynajmniej na początku. Ponieważ rozszerza tak daleko na zachód, to by ludzie myślą, że hej, może tam jest most lądowy, mimo wszystko (istota analogia, hej, może P  =  NP od tego nowego NP -Complete problemowych wygląda jak taki dobry kandydat na posiadające rozwiązanie czasu wielomianowego). Jednak po dokładnym zbadaniu Alaski i znalezieniu mostu lądowego ludzie prawdopodobnie byliby bardziej przekonani niż wcześniej, że Azja i Ameryka są oddzielone.

pytanie wprowadza szczególną analogię / metaforę, nieużywaną przez ekspertów i koncentruje się wyłącznie na P / NP i nie wspomina o innych klasach złożoności, podczas gdy eksperci postrzegają ją jako duży wzajemnie połączony wszechświat bytów, jak na niezwykłym diagramie stworzonym przez Kuperberga . dobrze byłoby skompilować dużą listę analogii klas złożoności, istnieje wiele takich analogii. mówi o „rozwiązaniu” problemów udowodnionych jako NP zakończone i „podekscytowaniu nowymi podejściami”.

można zrozumieć, że początkowe „podniecenie” przy odkryciu kompletnej klasy NP, ale pewne „podniecenie” zanikło po ponad czterdziestu latach intensywnego wysiłku, aby udowodnić, że P ≠ NP wydaje się nie pójść nigdzie obiecująco, a niektórzy badacze uważają, że my nie są bliżej. Historia jest pełna badaczy, którzy spędzili długie lata pracując nad problemami bez żadnego lub bardzo widocznego postępu, czasem z późniejszym żalem. więc NP zupełne może służyć (pożyczyć analogię Aaronsona) jako swego rodzaju „ogrodzenie elektryczne”, ostrzeżenie / zastrzeżenie, aby nie angażować się zbytnio w próby (tutaj dosłownie na wiele sposobów) „trudnych” problemów.

prawdą jest, że nadal istnieje poważny aspekt „katalogowania” kompletnych problemów NP. jednak trwają szeroko zakrojone badania „drobnoziarnistych” kluczowych kluczowych problemów NP (SAT, wykrywanie kliki itp.). (w rzeczywistości bardzo podobne zjawisko występuje z nierozstrzygalnymi problemami: raz udowodnione jako nierozstrzygalne, to tak, jakby były one rządzone „ziemią bez ludzi” do dalszych badań).

więc wszystkie problemy NP zupełne okazały się równoważne w stosunku do obecnej teorii, co czasami pokazuje uderzające przypuszczenia, takie jak hipoteza izomorfizmu Bermana-Hartmanisa . naukowcy mają nadzieję, że któregoś dnia to się zmieni.

to pytanie jest oznaczone soft-questionuzasadnieniem. poważni naukowcy nie omawiają zbyt wiele analogii w swoich pracach, które skłaniają się ku naukom popularnym , woląc zamiast tego skupić się na matematycznej precyzji / rygorze (jak podkreślono w wytycznych dotyczących komunikacji dla tej grupy). niemniej jednak pewna wartość ma tutaj edukacja i komunikacja z osobami postronnymi / świeckimi.

oto kilka „kontr-analogii” dla świeckich wraz z „badaniami prowadzącymi” do pojęć. można to zrobić z dłuższej listy.

• w pytaniu istnieje analogia terytoriów. ale bardziej sensowne jest myślenie o głównych regionach teorii złożoności, w tym w klasach znanych jako terra incognita . innymi słowy istnieje region P przecinający NP. zarówno P, jak i NP są dość dobrze zrozumiane, ale nie wiadomo, czy region P ⋂ NP-twardy (P przecina NP-twardy) jest pusty, czy nie.

• Aaronson podał ostatnio metaforę dwóch pozornie różnych rodzajów gatunków żab, które nigdy nie mieszają się dla P / NP. wspomniał także o „niewidzialnym ogrodzeniu elektrycznym” między nimi.

• fizyka cząstek elementarnych bada model standardowy. fizyka bada skład cząstek, podobnie jak teoria złożoności bada skład klas złożoności. w fizyce istnieje niepewność co do tego, w jaki sposób niektóre cząstki powodują powstawanie innych („ustalanie granic”), podobnie jak w teorii złożoności.

• „zoo złożoności” , jest jak wiele egzotycznych zwierząt, które mają różne możliwości, niektóre małe / słabe i niektóre duże / potężne.

• klasy złożoności są jak gładkie kontinuum czas / przestrzeń, jak widać w twierdzeniach o hierarchii czas / przestrzeń z kluczowymi „punktami przejścia” (zaskakująco dość głęboko analogicznymi do przejść fazowych materii fizycznej) między różnymi stanami.

• Maszyna Turinga to maszyna z „ruchomymi częściami”, a maszyny wykonują prace równoważne pomiarom energii i mają pomiary czasu / przestrzeni . więc klasy złożoności można postrzegać jako „energię” związaną z transformacjami wejścia-wyjścia czarnej skrzynki.

• istnieje wiele możliwych analogów z historii matematyki, np. problem kwadratury koła, znalezienia algebraicznych rozwiązań równania kwintycznego itp.

• Światy Impaggliazo

• Nowa książka Fortnows zawiera wiele analogii popularnej nauki dla górnictwa.

• Szyfrowanie / deszyfrowanie: Turing pracował nad tym w czasie II wojny światowej i wiele twierdzeń o różnicach w klasach złożoności może wydawać się analogicznych do problemów z deszyfrowaniem. jest to bardziej solidne dzięki papierom takim jak Natural Proofs, w których separacja klas złożoności jest bezpośrednio związana z „łamaniem” generatorów pseudolosowych liczb losowych.

• Kompresja / dekompresja: różne klasy złożoności umożliwiają / reprezentują różne poziomy kompresji danych. na przykład załóżmy, że P / poli zawiera NP. oznaczałoby to, że istnieją „mniejsze” jednostki (mianowicie obwody), które mogą „kodować” „większe” NP kompletne problemy, tj. większe (dane) struktury mogą być „skutecznie” skompresowane w mniejsze (dane) struktury.

• wzdłuż analogii zoo / zwierzę istnieje silny aspekt ślepca i słonia w teorii złożoności. pole jest najwyraźniej / prawdopodobnie we wcześniejszych stadiach bardzo długiego łuku (nie jest to nieprawdopodobne ani niespotykane w przypadku innych pól matematycznych o rozpiętości stuleci, a nawet tysiącleci), a wiele wiedzy można postrzegać jako częściowe, rozłączne i fragmentowane.

krótko mówiąc pytanie dotyczy „optymizmu związanego z redukcjami”. naukowcy zazwyczaj powstrzymują się od emocji, a czasem śmieją się z nich podczas czysto logicznych poszukiwań. istnieje równowaga zarówno długoterminowego pesymizmu, jak i ostrożnego optymizmu w tej dziedzinie i chociaż istnieje miejsce na nieformalność, wszyscy poważni badacze powinni dążyć do bezstronności w swoich postawach zawodowych w ramach opisu stanowiska pracy. co zrozumiałe, koncentruje się na małych zwycięstwach i inkrementalizmie i nie daje się „ponieść emocjom”.