Existência de Algoritmos com provas Não construtivas
# 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:
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:
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.