Wie kann man beweisen, dass 3-Farben entscheidend sind?

9

Um zu beweisen, dass 3-Färbung entscheidbar ist, reicht es zu sagen:

  • Jeder Knoten in der Grafik hat 3 mögliche Farben
  • Daher können wir alle Möglichkeiten aufzählen und dann überprüfen, ob keine zwei Kanten Knoten mit derselben Farbe verbinden3n

Beweist das, dass 3-Färbung entscheidbar ist? Oder muss ich eine Turing-Maschine bauen, um einen ordnungsgemäßen Beweis zu erhalten?

Beim 3-Färben spreche ich über das Problem der Diagrammfärbung; dh jedem Knoten in einem ungerichteten Diagramm eine von drei Farben zuweisen, sodass keine zwei benachbarten Knoten dieselbe Farbe haben.

computability turing-machines colorings Jenny
quelle
5
Das ist gut genug für mich. Übrigens, selbst wenn Sie sehr formell sein möchten, müssen Sie keine Turing-Maschine bereitstellen. Ein Programm in einer beliebigen Turing-vollständigen Sprache wird ausreichen. (In der Tat muss die Sprache nicht einmal Turing-vollständig sein, wir brauchen sie nur, um berechenbare Funktionen zu definieren.)
Yuval Filmus
Für die meisten Menschen ist dies der Fall. In einem Einführungskurs könnte dies nicht der Fall sein. Für einige Leute bedeutet "formaler Beweis" auch etwas anderes, was Sie vielleicht gesehen haben, wenn Sie einen Kurs über Logik belegt haben.
Yuval Filmus
@ YuvalFilmus Danke. Wie sieht ein "formaler Beweis" im Rahmen eines Logikkurses aus? Können Sie mich bitte auf ein Beispiel verweisen?
Jenny
@ Jenny Wenn Sie interessiert sind, nehmen Sie an einem Logikkurs teil.
Yuval Filmus
@YuvalFilmus Ich habe keinen Zugang zu einem Logikkurs. Gibt es ein Buch oder eine Online-Quelle, die Sie empfehlen können?
Jenny

Antworten:

10

Es hängt ganz davon ab, welchen Grad an Formalität Sie anstreben. Die informelle Beschreibung eines Algorithmus in Ihrer Frage reicht völlig aus, um mich davon zu überzeugen , dass die 3-Färbbarkeit entscheidbar ist. Wenn Sie etwas formeller sein möchten, können Sie einen Pseudocode angeben. Wenn Sie noch formeller sein möchten, können Sie eine Turing-Maschine auf Englisch beschreiben. Wenn Sie noch formeller sein möchten, können Sie die vollständige Beschreibung der Turing-Maschine aufschreiben und beweisen, dass sie wirklich über die 3-Färbbarkeit entscheidet.

Von den Optionen, die ich aufgelistet habe, ist es jedoch viel wahrscheinlicher, dass ein Fehler in der Beschreibung der Turing-Maschine oder in ihrem Korrektheitsnachweis vorliegt! Es ist also nicht klar, welcher Beweis am glaubwürdigsten wäre.

David Richerby
quelle
-5

Alle nicht deterministischen Probleme für TM sind entscheidbar. Aus Ihrer Beschreibung geht hervor, dass Sie Turing-Maschinen benötigen , um eine Lösung zu validieren. Ihre Erklärung ist also genug.3n

Juan Manuel Dato Ruiz
quelle
2
Hallo, willkommen bei CS. Leider scheint Ihr Beitrag die Frage nicht sinnvoll zu beantworten.
vonbrand