Como provar que a 3 cores é decidível?

9

Para provar que a 3 cores é decidível, basta dizer:

  • Cada nó no gráfico possui 3 cores possíveis
  • Portanto, podemos enumerar todas as possibilidades de e verificar se não há duas arestas conectando nós da mesma cor3n

Isso prova que a 3 cores é decidível? Ou preciso construir uma máquina de Turing para uma prova adequada?

Ao colorir 3, estou falando sobre o problema da coloração gráfica; ou seja, atribua uma das três cores a cada nó em um gráfico não direcionado, de modo que dois nós adjacentes não tenham a mesma cor.

computability turing-machines colorings Jenny
fonte
5
Isso é bom o suficiente para mim. A propósito, mesmo se você quer ser muito formal, não precisa fornecer uma máquina de Turing; um programa em qualquer idioma completo de Turing será suficiente. (Na verdade, a linguagem não precisa mesmo ser Turing completo, só precisamos para definir funções computáveis.)
Yuval Filmus
Para a maioria das pessoas, sim. Em um curso introdutório, talvez não. Além disso, para algumas pessoas, "prova formal" significa algo diferente, que você pode ter visto se fez um curso de lógica.
Yuval Filmus 01/01
@YuvalFilmus Thanks. Como é uma "prova formal" no contexto de um curso de lógica? Você poderia me indicar um exemplo, por favor?
Jenny
@ Jenny Se você estiver interessado, faça um curso de lógica.
Yuval Filmus 02/01
@YuvalFilmus Não tenho acesso a um curso de lógica. Existe um livro ou uma fonte on-line que você pode recomendar?
Jenny

Respostas:

10

Depende inteiramente do nível de formalidade que você deseja. A descrição informal de um algoritmo na sua pergunta é suficiente para me convencer de que a 3 cores é decidível. Se você quiser ser um pouco mais formal, pode dar o pseudocódigo. Se você ainda queria ser mais formal, poderia descrever uma máquina de Turing em inglês. Se você quiser ser ainda mais formal, escreva a descrição completa da máquina de Turing e prove que ela realmente decide a 3 cores.

Dito isto, das opções que listei, é bem mais provável que ocorra um erro na descrição da máquina de Turing ou em sua prova de correção! Portanto, não está claro qual prova seria a mais crível.

David Richerby
fonte
-5

3n

Juan Manuel Dato Ruiz
fonte
2
Olá, bem-vindo ao CS. Infelizmente, sua postagem não parece responder significativamente à pergunta.
vonbrand