Jaki jest naturalny problem w teorii obliczeń?

W pracy Stephena Cooka na temat problemu P vs NP [1] stwierdza, że ​​[2]:

Teza wykonalności: Naturalny problem ma wykonalny algorytm, jeśli ma algorytm czasu wielomianowego.

Moje pytanie brzmi: co dokładnie on (lub ogólnie tak naprawdę, co to znaczy) przez „ naturalny problem”? Mówienie o naturalnych problemach wydaje się dość powszechne, ale nie znalazłem jeszcze definicji. Wydaje mi się, że czegoś mi brakuje. Oto kilka możliwych odpowiedzi, o których myślę:

Pierwsza możliwa odpowiedź

Cook mówi w swoim artykule, że „naturalne” musi zostać wyjaśnione. Mówi: „generalnie nie uważamy, że klasa z parametrem jest tak naturalna, jak zbiór grafów, które można osadzić na powierzchni rodzaju k , k > 1.” [3] Po pierwsze, wydaje się, że to mówi „ „naturalne” nie jest raczej tym, czym jest; ale jeśli każdy problem jest albo naturalny, albo nie, a to w pełni opisuje wszystkie problemy, które nie są naturalne, wystarczyłoby, aby zdefiniować naturalny. (Ale kwalifikator „ogólnie” sugeruje, że nie jest to wystarczający i konieczny opis problemów, które nie są naturalne).

Wydaje mi się, że „klasy z parametrami” odnoszą się do ciągliwości parametrów o stałych parametrach, przez co rozumiemy problemy, które mają ograniczone możliwości wprowadzania danych, tak że wymuszona jest wykonalność. Możemy więc rozwiązać problem plecaka [4] za pomocą algorytmu czasu wielomianowego, jeśli naprawimy ciężar, który może unieść plecak (ale ogólnie nie ma rozwiązania w czasie wielomianowym). Biorąc to pod uwagę, uważam, że bycie „naturalnym” oznacza, że ​​problem nie jest ograniczony („sztucznie” ograniczony?) W sposób, który wymusza algorytm wielomianowy z problemu, którego nie można rozwiązać w czasie wielomianowym.

Powodem, dla którego nie jestem pewien, czy jest to właściwy sposób zrozumienia pojęcia Cooka o „naturalnym”, jest to, że nie jestem absolutnie pewien, co kwalifikują się tutaj „naturalne” kwalifikacje. Jeśli upuścisz „naturalny”, wtedy „problem ma wykonalny algorytm, jeśli ma algorytm wielomianowy”. Ale wydaje się to całkowicie uzasadnione: problem plecaka nie ma wykonalnego algorytmu, ponieważ nie ma algorytmu czasu wielomianowego; zdolność plecakowa z ustaloną paramaterą ma wykonalny algorytm, ponieważ ma algorytm czasu wielomianowego. Oba konta wydają się zgodne z pojęciem problemu z wykonalnym algorytmem.

Rozumiem, że może to być najlepszy przewodnik do zrozumienia, co znaczy Cook, ponieważ Cook faktycznie się odwraca i definiuje. Rozumiem również, że to pojęcie natury jest ujęte w tym pytaniu StackExchange. [5}

Ale jest inny.

Druga możliwa odpowiedź

William Gasarch w swoim artykule „Klasyfikowanie problemów w klasy złożoności” [6] mówi, że przeprowadzi „dosłowną dyskusję na temat naturalnego problemu” [7]. Na zakończenie pracy [8] odbywa się wymiana w formie dialogu, w której jeden z mówców mówi:

„Co sprawia, że ​​problem jest naturalny? Z jednej strony nie skonstruowałem problemu wyłącznie w celu nieobecności w P. Więc to nie jest głupi problem z dupą. Czy następnie podnosi się do poziomu bycia naturalnym?”

Wydaje mi się więc, że Gasarch mówi, że jeśli mamy problem, który nie jest celowo skonstruowany, abyśmy mogli powiedzieć, że nie ma go w P, to jest to naturalne. Tak więc przy odrobinie twórczej interpretacji wydaje się, że Gasarch mówi coś co najmniej spójnego z Cookiem: z jednej strony Gasarch mówi, że nie bycie skonstruowanym z jedynym celem nie będącym w P sprawia, że ​​problem nie jest naturalny; z drugiej strony Cook twierdzi, że problem jest naturalny, jeśli nie ma parametrów. Ale sama spójność nie daje definicji.

Trzecia możliwa odpowiedź

W artykule w Wikipedii dotyczącym „dobrze postawionego problemu” [9] przedstawiono definicję dobrze postawionego problemu przez Jacquesa Hadamarda, a następnie stwierdzono, że dobrze postawiony problem można uznać za „naturalny” problem w tym, że istnieją fizyczne procesy modelowane przez te problemy ”. Problem jest więc naturalny, czy tylko wtedy, gdy modeluje proces fizyczny?

Kwalifikacje Hadamarda, według Wikipedii, są następujące: (i) istnieje rozwiązanie, (ii) rozwiązanie jest unikalne, oraz (iii) zachowanie rozwiązania zmienia się w sposób ciągły wraz z warunkami początkowymi. Wydaje się, że różni się to od pozostałych dwóch definicji. Wydaje mi się, że „naturalne” nie jest używane dokładnie w ten sam sposób (zwłaszcza jeśli zgadzamy się z interpretacją, że problem jest naturalny tylko wtedy, gdy modeluje proces fizyczny), ale chciałem go uwzględnić, ponieważ wpadłem na w moich badaniach nad tym pytaniem, i są punkty kontaktowe.

Więc moje pytanie brzmi: co jest naturalnym problemem? Czy którakolwiek z tych odpowiedzi lub jakakolwiek ich kombinacja jest poprawna? Czy brakuje mi innej odpowiedzi? Dziękuję Ci.

1. „The Statement of the Problem”, 2006, opublikowane online w Clay Mathematics; tytuł: „The P vs. NP Problem”, http://www.claymath.org/sites/default/files/pvsnp.pdf
2. p. 3)
3. p. 4
4. https://en.wikipedia.org/wiki/Knapsack_problem#0.2F1_Knapsack_Problem
5. Najtrudniejszy znany problem naturalny w P Uważam, że naturalny problem wynika z tego opisu, ale nie ogranicza k do bycia największym.
6. https://www.cs.umd.edu/~gasarch/papers/classcomp.pdf
7. p. 2)
8. p. 47–8, sekcja 25
9. https://en.wikipedia.org/wiki/Well-posed_problem

Żeby było jasne, nie ma być sformalizowana. To nie jest twierdzenie, to obserwacja świata - jest w porządku, jeśli „naturalność” jest tutaj subiektywna. Dla analogii, jeśli ktoś mówi, że „różnicowanie to mechanika, a integracja to sztuka”, nie zaprasza cię do sformalizowania „mechaniki” i „sztuki” i udowodnienia stwierdzenia, starają się przekazać ogólną perspektywę. Być może brakuje ci trochę lasu dla drzew tutaj. [Przypis]

Jaki jest punkt autora

Postępujmy zgodnie z twoją sugestią i upuść słowo „naturalny”:

Teza wykonalności (pierwszy szkic): Problem ma wykonalny algorytm, jeśli ma algorytm czasu wielomianowego.

Jest to technicznie niewłaściwe. Ze względu na twierdzenie o hierarchii czasu możemy konstruować dowolnie trudne problemy w P (np. Wymagające czasu ). Ale te kontrprzykładowe problemy są bardzo dziwne, autoreferencyjne, np. „Czy dana maszyna Turinga zatrzymuje się na danych wejściowych w krokach ?”$n^{1000}$$n^{1000}$

Autor uważa więc, że teza jest nadal dość trafna w odniesieniu do problemów, które faktycznie chcemy rozwiązać w świecie rzeczywistym, oraz innych problemów napotkanych „naturalnie” w trakcie życia bez teorii złożoności. Tak więc myśli, nazwijmy te problemy „naturalnymi” i zrewiduj tezę wykonalności.

Co jest i nie jest naturalne

Z pewnością problem, który często pojawia się w praktyce, można uznać za naturalny: najkrótsze ścieżki, sortowanie, edycja odległości, wyszukiwanie korzeni, podróżny sprzedawca, plecak.

Z pewnością problem, który został przemyślany i zdefiniowany specjalnie w celu udowodnienia wyniku złożoności i odwołuje się do konkretnej klasy, nie jest naturalny. Na przykład „czy ten ciąg może zostać wygenerowany przez maszynę Turinga w stanach kw czasie n”.

Niektóre rzeczy są mniej jasne, na przykład programowanie liniowe, ale nie martwiłbym się tym zbytnio. Przestudiuj wiele algorytmów i problemów ze złożonością i sprawdź, czy zgadzasz się z ogólną ideą lub czy znajdziesz przykłady, które Twoim zdaniem są temu sprzeczne.

(W każdym razie uważam, że droga „dobrze postawionego problemu” jest zdecydowanie błędna, jak podejrzewasz).

[przypis] Nie chcę cię zniechęcać do próby sformalizowania, tylko do myślenia, że ​​masz to zrobić.

Z grubsza sprowadza się to do tego, czy definicja problemu może być okrągła:

• Sztuczny problem to taki, który spełnia kryteria swojej klasy.

• Naturalny problem nie polega na metodzie konstrukcji, która spełnia kryteria klasy.

Konstrukcja Ladnera jest znana jako NP-pośrednia , pod warunkiem, że istnieje NPI.

Udowodnienie, że jakikolwiek kandydat na naturalne problemy NPI okazałoby się .$P \subsetneq NP$

Uwaga: powodzenia w próbach udowodnienia takiego kandydata; To może wydawać się dostępnym podejściem, ale naturalnie stworzyło pewne bariery w dowodach .