Jak udowodnić, że 3-kolorowanie jest rozstrzygalne?

9

Czy w celu udowodnienia, że ​​3-zabarwienie jest rozstrzygalne, wystarczy powiedzieć:

  • Każdy węzeł na wykresie ma 3 możliwe kolory
  • Dlatego możemy policzyć wszystkie możliwości, a następnie sprawdzić, czy żadne dwie krawędzie nie łączą węzłów o tym samym kolorze3n

Czy to dowodzi, że 3-kolorowanie jest rozstrzygalne? Czy też muszę zbudować maszynę Turinga, aby uzyskać odpowiedni dowód?

Przez 3-kolorowanie mówię o problemie z kolorowaniem wykresów; tj. przypisz jeden z 3 kolorów do każdego węzła na niekierowanym wykresie, tak aby żadne dwa sąsiednie węzły nie miały tego samego koloru.

computability turing-machines colorings Przędzarka
źródło
5
To mi wystarczy. Nawiasem mówiąc, nawet jeśli chcesz być bardzo formalny, nie musisz dostarczać maszyny Turinga; wystarczy program w dowolnym języku kompletnym Turinga. (Rzeczywiście, język nie musi być nawet kompletny w Turinga, potrzebujemy go tylko do zdefiniowania funkcji obliczalnych.)
Yuval Filmus
Dla większości ludzi tak jest. W kursie wprowadzającym może nie być. Ponadto dla niektórych osób „dowód formalny” oznacza coś innego, co mógłbyś zobaczyć, gdybyś wziął kurs logiki.
Yuval Filmus
@YuvalFilmus Thanks. Jak wygląda „formalny dowód” w kontekście kursu logicznego, czy mógłbyś mi wskazać przykład?
Jenny
@Jenny Jeśli jesteś zainteresowany, weź kurs logiki.
Yuval Filmus
@YuvalFilmus Nie mam dostępu do kursu logicznego, czy istnieje książka lub źródło internetowe, które możesz polecić?
Jenny

Odpowiedzi:

10

Zależy to całkowicie od tego, do jakiego poziomu formalności dążysz. Nieformalny opis algorytmu w twoim pytaniu wystarczy, aby przekonać mnie, że 3-kolorowalność jest rozstrzygalna. Jeśli chcesz być bardziej formalny, możesz podać pseudokod. Jeśli chcesz być bardziej formalny, możesz opisać maszynę Turinga po angielsku. Jeśli chcesz być jeszcze bardziej formalny, możesz zapisać pełny opis maszyny Turinga i udowodnić, że naprawdę decyduje o 3-kolorowalności.

Powiedziawszy to, spośród wymienionych przeze mnie opcji, jest o wiele bardziej prawdopodobne, że wystąpi błąd w opisie maszyny Turinga lub w jej dowodzie poprawności! Nie jest więc jasne, który dowód byłby najbardziej wiarygodny.

David Richerby
źródło
-5

Wszystkie niedeterministyczne problemy związane z TM są rozstrzygalne, więc z opisu wykazałeś, że potrzebujesz maszyn do sprawdzania poprawności rozwiązania. Twoje wyjaśnienie wystarczy.3n

Juan Manuel Dato Ruiz
źródło
2
Cześć, witamy w CS. Niestety, twój post nie wydaje się sensownie odpowiadać na pytanie.
vonbrand