Ist dieses Problem mit endlichen Graphen entscheidbar? Welche Faktoren machen ein Problem entscheidbar?

Ich möchte wissen, ob das folgende Problem entscheidbar ist und wie man es herausfindet. Jedes Problem, das ich sehe, kann ich mit "Ja" oder "Nein" beantworten. Sind die meisten Probleme und Algorithmen mit Ausnahme einiger weniger entscheidbar (was hier angegeben ist )?

Eingabe: Ein gerichteter und endlicher Graph mit und als Eckpunkten Frage: Existiert ein Pfad in mit als anfänglichem Eckpunkt und als endgültigem Eckpunkt?$G$$v$$u$
$G$$u$$v$

Jedes Problem, bei dem nur eine begrenzte Datenmenge untersucht werden muss, kann entschieden werden, da es einen Algorithmus gibt, der darin besteht, alle möglichen Lösungen aufzulisten. Es mag lächerlich langsam sein, aber das ist nicht relevant: Wenn es einen Algorithmus gibt, ist er entscheidbar.

Das Problem, das Sie angeben, geht von einem endlichen Graphen aus, der stark darauf hindeutet, dass es entscheidbar ist. Genau genommen muss man ein bisschen weiter schauen. Das Problem ist eine Eigenschaft der Pfade im Diagramm, und manchmal gibt es unendlich viele Pfade, wenn das Diagramm einen Zyklus enthält (Sie können diesen Zyklus beliebig oft durchlaufen). Es ist jedoch einfach, das Problem in ein endliches Problem umzuwandeln: Wenn es einen Pfad gibt, der mit beginnt und mit v endet und einen Zyklus enthält, können Sie alle Zyklen in diesem Pfad ausschneiden, und Sie haben eine neue Lösung, die dies tut keinen Zyklus enthalten. Da es eine endliche Anzahl von Pfaden gibt, die keinen Zyklus beinhalten (wenn der Graph k Kanten hat, gibt es höchstens k $u$$v$$k$$k!$Pfade, die dieselbe Kante nicht mehr als einmal verwenden, ist das Problem, einen Pfad von nach v zu finden, endlich und kann daher entschieden werden.$u$$v$

Diese Eigenschaft wird übrigens Konnektivität genannt .

Dieser Ansatz ist weit verbreitet und wird als Reduktion bezeichnet . Angesichts eines Problems, das nicht einfach ist, haben wir es auf ein Problem reduziert, das wir zu lösen wussten.

Es ist oft schwierig zu beweisen, dass ein Problem unentscheidbar ist. Um zu beweisen, dass ein Problem entscheidbar ist, müssen wir nur einen Algorithmus zeigen, der es entscheidet. Um zu beweisen, dass ein Problem unentscheidbar ist, müssen wir beweisen, dass kein Algorithmus existieren kann. Es gibt einige bekannte, unentscheidbare Probleme. In der Praxis zeigen wir die meiste Zeit, wenn wir beweisen, dass ein Problem unentscheidbar ist, dass es ein bekanntes unentscheidbares Problem gibt, das sich auf unser Problem reduziert. Da ein Algorithmus für unser Problem das bekannte unentscheidbare Problem lösen würde, muss unser Problem auch unentscheidbar sein.

Man kann nicht wirklich sagen, dass „die meisten“ Probleme entscheidbar oder „die meisten“ Probleme unentscheidbar sind. In gewissem theoretischen Sinne sind fast alle Probleme unentscheidbar, aber wir tendieren stark dazu, „interessante“ Probleme anzugehen, und diese haben mit größerer Wahrscheinlichkeit eine Lösung.

Das Problem ist trivial zu entscheiden, worauf Gilles in einem Kommentar hingewiesen hat. Wie für Ihre andere Frage ...

Sind die meisten Probleme und Algorithmen mit Ausnahme einiger weniger entscheidbar (was hier angegeben ist )?

Nee. Tatsächlich sind die meisten Probleme unentscheidbar. Tatsächlich gibt es unzählige Probleme (Sprachen), aber es gibt nur unzählige Turingmaschinen, was bedeutet, dass es höchstens unzählige entscheidbare Probleme gibt.

Ja, dies ist entscheidend, da Sie alle möglichen Pfade vollständig durchsuchen können. Es müssen keine Pfade betrachtet werden, die einen Scheitelpunkt wiederholen, da der "Umweg" übersprungen werden könnte. Die Länge eines sich nicht wiederholenden Pfades wird jedoch durch die Größe des Graphen begrenzt, der endlich ist, und daher gibt es nur endlich viele solcher Pfade, die einzeln überprüft werden können.

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

Es gibt keine Methode, die Ihnen sagt, ob ein bestimmtes Problem entscheidbar ist oder nicht. Mit der Zeit könnten Sie eine gute Ahnung bekommen, ob ein bestimmtes Problem entscheidbar ist oder nicht.

Was ich normalerweise mache, ist das Folgende:

1. versuchen Sie das Problem zu lösen. Versuchen Sie also, sich ein Computerprogramm vorzustellen, mit dem das gegebene Problem gelöst werden kann. Für Ihr vorgeschlagenes Problem - ein sehr einfaches Programm überprüft nur einen möglichen Pfad und findet ihn daher immer wieder (falls vorhanden) oder teilt Ihnen mit, dass kein anderer Pfad vorhanden ist.
2. formulieren Sie das Problem klar. Viele Probleme sind einfach zu vage, aber wenn sie klar geschrieben sind, ist es sehr leicht zu erkennen, ob sie entscheidbar sind oder nicht (im Vergleich zu anderen Problemen, die als unentscheidbar / entscheidbar bekannt sind oder bekannte Methoden wie den Satz von Rice verwenden ).
3. Wenn (2) nicht funktioniert hat, Sie aber immer noch glauben, dass das Problem nicht entschieden werden kann, versuchen Sie, es zu beweisen, indem Sie es von einem nicht entschiedenen Problem abbauen (das Halteproblem (oder seine Ergänzung) funktioniert in vielen Fällen).

Fast immer, wenn Sie versuchen, Schritt (1) für ein unentscheidbares Problem auszuführen, müssen Sie mit Ihrem Programm unendlich viele Dinge überprüfen . Dies ist normalerweise ein Zeichen dafür, dass das Problem nicht entschieden werden kann.