Existência de Algoritmos com provas Não construtivas

A maioria dos resultados positivos sobre problemas computacionais são provas construtivas, i.e. , um problema computacional é provado pra ser solucionado a partir de um algoritmo que o resolve; um problema computacional mostra-se em P(complexidade) dado que a partir da sua entrada tenha um algoritmo que o resolve em tempo polinomial; etc.

No entanto, existem vários resultados não- construtivos, onde a existência de um algoritmo é provada sem mostrar o algoritmo por si só. Várias técnicas são usadas para fornecer a existências dessas provas.

Usando um conjunto finito desconhecido

Em teoria combinatória dos jogos

Um simples exemplo de um algoritmo não construtivo publicado em 1982 por Elwyn R.Berlekamp, John H.Conway, e Richard K.Guy , no livro Winning Ways for your Mathematical Plays. Trata-se de um jogo de Sylver Coinage, no qual jogadores se revezam especificando um inteiro positivo que não pode ser expresso como a soma de valores especificados antes, tendo um perdedor quando eles são forçados a  especificar o número 1.Existe um algoritmo (dado no livro como um fluxograma) para determinar se um dado primeiro movimento é vencedor ou perdedor :se um número primo é maior do que 3, ou um conjunto finito de números 3-smooth, então é a primeira jogada é de um ganhador, e caso contrário é um perdedor. No entanto, o conjunto finito não é conhecido.

Em teoria dos grafos

Não construtivas provas para problemas em teoria dos grafos são estudadas desde 1988 por Michael Fellows e Michel Langston.

Uma questão comum em teoria dos grafos é se uma certa entrada tem uma certa propriedade.Por exemplo:

Entrada: Um grafo G

Problema: G pode ser incorporado em um espaço 3-dimensional, de tal modo que não existem dois ciclos dijuntos de G que são topologicamente ligados (como uma cadeia ligada)?

Existe um algoritmo exponencial de alto grau que decide se dois ciclos incorporados em um espaço 3-d são ligados, e se um destes poderia testar todos os pares de ciclos no grafo ,mas se não está obvio como contabilizar todas as possíveis incorporações no espaço 3-d. Deste modo, não estará claro a priori se o problema da ligação é decidível.

No entanto, existe uma prova não construtiva que mostra que o problema da ligação é decidível em tempo polinomial. A prova conta com os seguintes fatos:

• O conjunto de grafos para cada resposta “sim” é fechado sob minor, i.e.,se um grafo G pode ser incorporado ao problema da ligação.
• Para cada dois grafos G e H, é possível achar um tempo polinomial se H é um menor de G.
• Pelo teorema de Robertson-Seymour, qualquer conjunto finito de grafos contém um só número finito minor minimo de elementos. Em particular, o conjunto de instâncias de “sim” tem um número finito de elementos minor minimo.

Dado de entrada o grafo G, o seguinte “algoritmo” resolve o problema:

Para cada elemento  minor- minimal H:

Se H é um menor de G então retorne “sim”

retorne “não”.

A parte não-construtiva é do teorema de Robertson-Seymour. Embora garanta que existe um número finito de elementos que são minor minimo não fala sobre quais são esses elementos. Portanto, não pode-se realmente executar o “algoritmo” mencionado acima. Mas, sabe-se da existência do algoritmo e que roda em tempo polinomial;

Existem muito mais problemas similares nos quais a decidibilidade pode ser provada do mesmo modo. Em alguns caso, o conhecimento de que um problema pode ser provado em um tempo polinomial levou pesquisadores a procurar e achar um algoritmo que roda em tempo polinomial atual que resolve o problema de uma forma totalmente diferente. Isto mostra que provas não - construtivas podem ter resultados construtivos.

A ideia principal é que um problema pode ser resolvido usando um algoritmo que usa como parâmetro , um conjunto desconhecido. Embora o conjunto seja desconhecido, pode-se saber que ele deve ser finito, e existindo assim um algoritmo de tempo polinomial.

Existem vários outros problemas combinatórios que podem ser resolvidos com uma técnica similar.

Contando os algoritmos

As vezes o número de potenciais algoritmos para um dado problema é finito.Pode -se contar o número de possíveis algoritmos  e provas que somente um número limitado deles são “ruins” então pelo menos um algoritmo deve ser “bom”. Como exemplo, considere o seguinte problema.

Selecione um vetor v composto por n elementos que são inteiros entre 0 e uma certa constante d.

Você tem que adivinhar v solicitando consultas de soma , nos quais são consultas da forma: “Qual é a soma dos índices i e j ?”. Uma consulta de soma pode se relacionar para qualquer número de índices de 1 até n.

Quantas consultas precisam ? Obviamente, n consultas sempre são suficientes, porque não se pode usar n consultas solicitando“soma” de um único elemento. Mas quando d é pequeno suficiente é possível fazer melhor. A ideia geral é a seguinte.

Toda consulta pode ser representada como vetor de 1 para n cujos elementos são todos do conjunto {0,1}; o conjunto de respostas é o produto da matriz por v.

Uma matriz M é “boa” se ela nos permite identificar exclusivamente v. Significa que, para casa vetor v, o produto de M v é diferente. Uma matriz M é “ruim” se existem dois vetores diferentes v e u tal que M v = M u.

Usando um pouco de álgebra, é possível limitar o número de matrizes “ruins”. O limite é a função de d e k. Portanto, para um d suficientemente pequeno, deve haver uma matriz “boa” com um k pequeno, que corresponde a um algoritmo para resolver o problema de identificação.

Esta prova é não - construtiva por dois motivos : Não se sabe como achar uma boa matriz; e mesmo uma boa matriz é fornecida, não se sabe como reconstruir um vetor com as respostas da consulta.

Existem muito mais problemas similares provados que podem ser resolvidos de manira similar.

Exemplos Adicionais

• Alguns problemas computacionais podem ser demonstrados para ser decidíveis usando a lei do terceiro excluído. Tais provas são normalmente não usuais na prática, uma vez que os problemas envolvidos são bastante artificiais.
• Um exemplo para a teoria da complexidade quântica( relatado para Complexidade de consultas quânticas) é dada em.

Créditos

As referências desta página foram coletadas de tópicos do Stack Exchange:

• "Existem problemas que não tem algoritmos eficiente , onde existem teoremas que provam que esses algoritmos existem?"CS Theory Stack Exchange. Retrieved 21 November 2014.
• "Existem algoritmos com provas não construtivas?".CS Theory Stack Exchange. Retrieved 21 November 2014.
• "Existe um algoritmo que provavelmente existe embora não sabemos o que é?"Computer Science Stack Exchange. Retrieved21 November 2014.

Veja também

• Existence theorem#'Pure' existence results

• Constructive proof#Non-constructive proofs