A classe co-RE, entretanto, é composta pelos problemas para os quais alguma máquina de Turing responderia "não" em um tempo finito; essa é a classe dos problemas tratáveis (parava resposta "não"). Um exemplo de problema co-RE é o problema do dominó usando os ladrilhos de Wang de forma periódica (mais detalhes).
A classe R é composta pelos problemas que sempre se tem a resposta, seja ela "sim" ou "não", em um tempo finito (por isso que ela é a interseção entre RE e co-RE); essa é a classe dos problemas decidíveis. Um problema que está contido em R (e também contido em NP, um subconjunto muito pequeno e restrito de R) é o problema do caminho hamiltoniano. Sua versão de decisão é assim: dado um grafo G (com arestas ponderadas) e um número k, eu consigo passar por todos os vértices de G apenas uma única vez de modo que meu caminho tenha peso menor do que ou igual a k?
Quando se trabalha com grafos (e, por consequência, com árvores), precisamos encontrar alguma condição. Existem diversos tipos de condições a serem encontradas, mas normalmente se dividem no seguinte:
Muitos algoritmos partem de um único ponto, já outros partem de diversos pontos (Floyd-Warshall parte de todos os vértices ao mesmo tempo ¯\_(ツ)_/¯).
Para os que partem de alguma origem única, ele precisa determinar como visitar os vértices vizinhos para, então, continuar a busca. Então, precisa ir para os vizinhos dos vizinhos e assim sucessivamente.
A busca em largura visita, por vez, todos os vértices de uma determinada profundidade (relacionada). Já a em profundidade, não, vai até o fim de um caminho para então tentar um caminho alternativo.
Dado um mapa, onde . significa espaço livre, # significa parede intransponível, s a saída e i a sua posição incial, é possível sair do labirinto?