Existem problemas sem algoritmos eficientes, onde os teoremas da existência provaram que esses algoritmos devem existir?

22

Existem problemas no CS em que não são conhecidos algoritmos eficientes, apesar dos teoremas da existência provar que esses algoritmos eficientes devem existir?

Como são chamados esses problemas? Onde posso descobrir mais?

ds.algorithms reference-request terminology z5h
fonte
4
Eu acho que isso é relevante: en.wikipedia.org/wiki/Minor_(graph_theory)#Algorithms
Philip White
3
Qual a sua pergunta? No título diz "soluções", mas no conteúdo você escreve "algoritmos".
Marcos Villagra
6
Eu acho que seria melhor se você pedir problemas interessantes / naturais , caso contrário, é fácil definir tais problemas: faça qualquer declaração matemática que não seja verdadeira ou falsa, faça com que o problema seja 1 (independente da entrada), se for verdadeiro e 0 se for falso. Existem dois algoritmos muito simples que um deles resolve esse problema, mas decidir qual é basicamente provar / refutar a afirmação matemática, por isso não sabemos qual a resolver.
Kaveh

Respostas:

9

Como exemplo, Shelby Kimmel usa o método adversário neste documento para mostrar que deve existir algoritmo de consulta O ( 1 ) para um determinado problema para o qual não conhecemos uma solução de consulta constante. Ela faz isso de maneira particularmente eficiente, localizando a complexidade da consulta do problema composto por si d vezes e, em seguida, localizando a complexidade da consulta Q da função composta, e observando que a complexidade da consulta da função original está na ordem Q 1O(1)dQ .Q1d

Artem Kaznatcheev
fonte
12

Claro, existem muitos exemplos, pelo menos no espírito da sua pergunta.

Frequentemente, obtém-se esse resultado do método probabilístico . Por exemplo, um artigo de que gosto é o de reconstruir gráficos no modelo aditivo . Aqui, os autores mostram que existe um conjunto de consultas que irão (otimamente) aprender o gráfico de destino. Dado esse conjunto, o algoritmo é eficiente. No entanto, eles usam o método probabilístico para mostrar a existência desse pequeno conjunto (para cada tamanho de problema) que funcionará em todas as entradas, mas não o constrói explicitamente. Portanto, o melhor que eles podem fazer é apenas uma pesquisa de força bruta através de uma família exponencial de consultas, porque elas não têm uma construção explícita.O(dn)

Lev Reyzin
fonte
2

Não, você sempre pode usar o algoritmo mais rápido e mais curto para todos os problemas bem definidos . ;)

Marcus Ritt
fonte
Eu não estava falando sério, mas observe que a construção de Hutter realmente prova a correção do algoritmo. Por que você acha que não responde à pergunta?
Marcus Ritt
4
@ Ross Snider: é claro que linguagens indecidíveis escapam ao resultado de Hutter: afinal, ele está dando um algoritmo! No entanto, diferentemente da pesquisa Levin, que exige que as instâncias de problemas tenham certificados verificáveis ​​(como problemas de pesquisa NP), a pesquisa de Hutter não. Requer apenas que o problema seja declarado em uma linguagem formal, que possa servir de base para a busca exaustiva de provas [de que alguma MT está de fato resolvendo o problema especificado]. Além disso, Hutter / Levin não nos fornece provas de existência de algoritmos eficientes para um problema, a menos que já saibamos que o problema possui esse algoritmo.
Joshua Grochow 08/02/11
1
@ Josué Criei linguagens indecidíveis como um exemplo de algo que a pesquisa de Hutter / Levin não poderia decidir (tentei escolher algo óbvio), mas que permanece "bem definido"; é um argumento contra a reivindicação empreendida no título do trabalho. Claro, tive o cuidado de admitir que não havia lido o conteúdo, o que terei que fazer agora.
Ross Snider
1
Esse algoritmo é o conteúdo computacional da equivalência da matemática construtiva e clássica em afirmações que já existem?
Neel Krishnaswami
1
@ Neel Kirshnaswami: É difícil dizer, já que eu não sabia que havia essa equivalência! Você pode dar um ponteiro?
Joshua Grochow
1

Edit: A resposta abaixo está registrando a existência de soluções para um determinado problema computacional, não a existência de algoritmos. Inicialmente, interpretei mal a pergunta.

Responda

Há uma classe de complexidade que captura esse tipo de problemas computacionais. É conhecido como TFNP . Foi definido neste artigo:

Nimrod Megiddo e Christos Papadimitriou. Em funções totais, teoremas de existência e complexidade computacional . Ciência da Computação Teórica 81 (2): 317-324.

Aqui você encontrará problemas como o Triângulo Tricromático, para os quais a existência de uma solução é garantida pelo Lema de Sperner (consulte o documento para a definição deste problema).

Você também tem o seguinte documento:

Christos Papadimitriou. Sobre a complexidade do argumento de paridade e outras provas ineficientes de existência . Journal of Computer and Systems Science 48 (3), 1990.

Neste documento, você encontrará:

  • n
  • Equilíbrio de jogos para 2 jogadores.
  • Encontre um segundo caminho hamiltoniano em um gráfico.

O artigo tem muitos exemplos desse tipo de problema. Então eu recomendo dar uma olhada nisso.

Marcos Villagra
fonte
2
A pergunta não se refere a problemas com soluções comprovadamente existentes para suas versões de decisão, mas a problemas com existência comprovada de algoritmos eficientes. Essas são coisas diferentes. Concordo que, à primeira vista, o título pode induzir em erro. No entanto, apenas à primeira vista.
Oleksandr Bondarenko
sim, eu também concordo. Mas eu estava totalmente enganado com a pergunta. Agora, neste caso, a resposta é enganosa. O que eu faço? Eu excluo a pergunta? Ou edite e coloque um aviso sobre o que exatamente está respondendo?
Marcos Villagra
Não há políticas para excluir respostas; você sempre pode fazer o que considerou apropriado. Pessoalmente, acho que é bom deixar sua resposta aqui. Você pode fazer uma declaração sobre qual pergunta está respondendo exatamente.
Hsien-Chih Chang #