Czy problem grafu skończonego jest rozstrzygalny? Jakie czynniki decydują o problemie?

Chcę wiedzieć, czy można rozwiązać następujący problem i jak się dowiedzieć. W każdym problemie, który widzę, mogę powiedzieć „tak” lub „nie”, więc czy większość problemów i algorytmów można rozstrzygać, z wyjątkiem kilku (które podano tutaj )?

Wejście: kierowane i skończonych wykres z i , jak wierzchołki Pytanie: Czy ścieżką w o w początkowym wierzchołek i jako końcowy wierzchołek istnieje?v u G u $G$$v$$u$
$G$$u$$v$

Każdy problem wymagający jedynie zbadania skończonej ilości danych jest rozstrzygalny, ponieważ istnieje algorytm polegający na wyliczeniu wszystkich potencjalnych rozwiązań. Może być absurdalnie wolny, ale nie ma to znaczenia: jeśli istnieje algorytm, można go rozstrzygać.

Podany problem zakłada skończony wykres, który wyraźnie wskazuje, że można go rozstrzygać. Ściśle mówiąc, musisz spojrzeć nieco dalej. Problemem jest właściwość ścieżek na wykresie, a czasami istnieje nieskończona liczba ścieżek, gdy wykres zawiera cykl (możesz zapętlać ten cykl tyle razy, ile chcesz). Łatwo jest jednak przekształcić problem w problem skończony: jeśli istnieje ścieżka zaczynająca się od a kończąca się na v, która zawiera cykl, możesz wyciąć wszystkie cykle na tej ścieżce i masz nowe rozwiązanie, które nie obejmują cyklu. Ponieważ istnieje skończona liczba ścieżek, które nie obejmują cyklu (jeśli wykres ma k krawędzi, istnieje co najwyżej k $u$$v$$k$$k!$ścieżki, które nie używają tej samej krawędzi więcej niż raz), problem ze znalezieniem ścieżki od do v jest skończony, a zatem rozstrzygalny.$u$$v$

Nawiasem mówiąc, ta właściwość nazywa się łącznością .

Takie podejście jest powszechne, zwane redukcją . Biorąc pod uwagę problem, który nie jest prosty, zredukowaliśmy go do problemu, który potrafiliśmy rozwiązać.

Często trudno jest udowodnić, że problem jest nierozstrzygalny. Aby udowodnić, że problem jest rozstrzygalny, wystarczy pokazać algorytm, który go rozstrzygnie. Aby udowodnić, że problem jest nierozstrzygalny, musimy udowodnić, że nie istnieje żaden algorytm. Istnieje kilka dobrze znanych nierozstrzygalnych problemów. W praktyce przez większość czasu, gdy dowodzimy, że problem jest nierozstrzygalny, pokazujemy, że istnieje dobrze znany nierozstrzygalny problem, który ogranicza się do naszego problemu. Ponieważ algorytm naszego problemu rozwiązałby dobrze znany nierozstrzygalny problem, nasz problem również musi być nierozstrzygalny.

Naprawdę nie można powiedzieć, że „większość” problemów jest rozstrzygalnych lub „większość” problemów jest nierozstrzygalnych. W pewnym sensie teoretycznym prawie wszystkie problemy są nierozstrzygalne, ale mamy silną tendencję do rozwiązywania „interesujących” problemów, a te są bardziej prawdopodobne, że znajdą rozwiązanie.

Problem jest trywialnie rozstrzygalny, jak zauważył Gilles w komentarzu. Co do twojego drugiego pytania ...

czy można rozstrzygać większość problemów i algorytmów z wyjątkiem kilku (które są tutaj podane )?

Nie. W rzeczywistości większość problemów jest nierozstrzygalna. W rzeczywistości istnieje niezliczona ilość problemów (języków), ale istnieje tylko wiele maszyn Turinga, które można policzyć, co oznacza, że ​​istnieje co najwyżej wiele możliwych do rozstrzygnięcia problemów.

Tak, jest to rozstrzygalne, ponieważ możesz przeprowadzić wyczerpujące wyszukiwanie wszystkich możliwych ścieżek. Nie ma potrzeby patrzeć na ścieżki, które powtarzają wierzchołek, ponieważ „objazd” można pominąć. Ale długość każdej niepowtarzalnej ścieżki jest ograniczona przez rozmiar wykresu, który jest skończony, a więc istnieje tylko skończenie wiele takich ścieżek, które można sprawdzić jeden po drugim.

$G$$a$$b$$a$$b$

Nie ma metody, która mówi, czy konkretny problem jest rozstrzygalny, czy nie. Z czasem możesz uzyskać dobre przeczucie, niezależnie od tego, czy określony problem jest rozstrzygalny.

Zwykle robię to:

1. spróbuj rozwiązać problem. Oznacza to, że pomyśl o programie komputerowym, który rozwiązuje dany problem. W przypadku zasugerowanego problemu - bardzo prosty program po prostu sprawdzi każdą możliwą ścieżkę, a zatem zawsze będzie w stanie ją znaleźć (jeśli istnieje) lub powie, że żadna ścieżka nie istnieje inaczej.
2. jasno sformułuj problem. Wiele problemów jest po prostu zbyt niejasnych, ale gdy jest napisane jasno, bardzo łatwo jest sprawdzić, czy można je rozstrzygać, czy nie (porównując z innymi problemami, o których wiadomo, że są nierozstrzygalne lub stosując znane metody, takie jak twierdzenie Rice'a )
3. Jeśli (2) nie działało, ale nadal uważasz, że problem jest nierozstrzygalny, spróbuj udowodnić go poprzez redukcję problemu nierozstrzygalnego (problem zatrzymania (lub jego uzupełnienia) działa w wielu przypadkach).

Prawie zawsze, gdy próbujesz wykonać krok (1) dla nierozwiązywalnego problemu, będziesz potrzebować twojego programu do sprawdzenia nieskończonej liczby rzeczy. Zazwyczaj jest to znak, że problem nie podlega rozstrzygnięciu.