Dlaczego problemy decyzyjne są powszechnie stosowane w teorii złożoności?

Z Wikipedii :

Rodzaj problemu obliczeniowego: Najczęściej stosowanymi problemami są problemy decyzyjne . Klasy złożoności można jednak zdefiniować na podstawie problemów z funkcjami, problemów z liczeniem, problemów z optymalizacją, problemów z obietnicą itp.

Widziałem także definicje NP-zupełne, NP-twarde, NP, ..., zdefiniowane tylko dla problemów decyzyjnych. Zastanawiam się, dlaczego tak jest?

Czy to dlatego, że jakikolwiek inny problem można w sposób równoważny przekształcić w problem decyzyjny?

Często stosuje się problemy decyzyjne, ponieważ pozwalają one na precyzyjną i prostą definicję problemu i, jak stwierdzono, wiele innych problemów można przekształcić w równoważny problem decyzyjny.

Inne typy problemów są również uwzględniane w teorii złożoności, na przykład problemy z funkcją i problemy z wyszukiwaniem .

prawdopodobnie istnieje wiele różnych sposobów odpowiedzi na to pytanie, jednak jednym z kluczowych elementów jest precedens historyczny. rozrzut istnienia algorytmu dla problemu zatrzymania w 1936 r. przez Turinga wykorzystuje problem zatrzymania jako problem decyzyjny. było to z kolei oparte na (i rozwiązane negatywnie) Hilberts Entscheidungsproblem (1928), która poprosiła o systematyczną metodę ustalania prawdy lub fałszu każdego dobrze sformułowanego stwierdzenia matematycznego, tj. również problemu decyzyjnego.

to z kolei ma pewne podobieństwo do 10. problemu Hilberta z 1900 r., który wymaga rozwiązania równań całkowitych diofantycznych (wiele z jego 23 zagadnień granicznych / kluczowych stanowiło problemy decyzyjne). zauważ jednak Entscheidungsproblem, nawet zakorzeniony w znacznie wcześniejszej koncepcji Leibniza, jak głosi wikipedia:

Geneza Entscheidungsproblem sięga Gottfrieda Leibniza, który w XVII wieku, po zbudowaniu udanej maszyny do obliczeń mechanicznych, marzył o zbudowaniu maszyny, która mogłaby manipulować symbolami w celu ustalenia prawdziwych wartości matematycznych stwierdzeń.

zauważcie również, że równania diofantyczne pochodzą od Greków, którzy byli jednymi z pierwszych, którzy brali pod uwagę, studiowali i podkreślali wagę dowodu matematycznego. istnieją co najmniej dwa ważne problemy z teorii liczb, wciąż nierozwiązane dzięki wielu nowoczesnym badaniom, ze względu na Greków: istnienie nieskończonych liczb pierwszych bliźniaczych i istnienie liczb nieparzystych idealnych .

zwróć uwagę, że niektóre „problemy decyzyjne” (tj. w postaci poszukiwania dowodów do otwarcia domysłów matematycznych) dosłownie zajęły setki lat, np. ostatnie twierdzenie Fermata , ponad 3,5 wieku, również w teorii liczb.

więc problemy decyzyjne są bardzo stare, ale nawet jeśli po prostu stwierdzone, mogą być niezwykle trudne i są zasadniczo zakorzenione w pytaniu „czy to stwierdzenie jest prawdziwe czy fałszywe” w stosunku do istnienia dowodów (dowodów). w sercu jest to podstawowa koncepcja matematyczna. co więcej, pojawia się ponownie w nowoczesnych miejscach w fundamentalny i przypominający sposób, np. pytanie P vs NP (~ 1971), gdzie klasa NP może być zdefiniowana / sformułowana w kategoriach zatrzymania maszyny NP i rozwiązania problemu satysfakcji w czasie P .