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”.