Existência de Algoritmos com provas Não construtivas

Origem: Wikipédia, a enciclopédia livre.

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[editar | editar código-fonte]

Em teoria combinatória dos jogos[editar | editar código-fonte]

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[editar | editar código-fonte]

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

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 o 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.[1]

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.[2]

Contando os algoritmos[editar | editar código-fonte]

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.[3]

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.[3]

Exemplos Adicionais[editar | editar código-fonte]

Referências

  1. a b Fellows, M. R; Langston, M. A (1988). "Nonconstructive tools for proving polynomial-time decidability. [S.l.]: Journal of the ACM 35 (3): 727. doi:10.1145/44483.44491 
  2. Brown, D. J.; Fellows, M. R.; Langston, M. A. (2007). «Polynomial-time self-reducibility: Theoretical motivations and practical results∗». International Journal of Computer Mathematics. 31. 1 páginas. doi:10.1080/00207168908803783 
  3. a b Grebinski, V; Kucherov, G. (2000). «Optimal Reconstruction of Graphs under the Additive Model». Algorithmica. 28. 104 páginas. doi:10.1007/s004530010033 
  4. Kimmel, S. (2013). «Quantum Adversary (Upper) Bound». Chicago Journal of Theoretical Computer Science. 19: 1-14. doi:10.4086/cjtcs.2013.004 

Créditos[editar | editar código-fonte]

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

Veja também[editar | editar código-fonte]