Problemas que são contra-intuitivamente solucionáveis ​​na prática?

21

Recentemente, passei pela dolorosa experiência divertida de explicar informalmente o conceito de complexidade computacional a um jovem programador autodidata talentoso, que nunca havia feito um curso formal de algoritmos ou complexidade antes. Não surpreendentemente, muitas noções pareciam estranhas a princípio, mas faziam sentido em alguns exemplos (PTIME, intratabilidade, incomputabilidade) , enquanto outras parecem vir mais naturais (classificação de problemas por reduções, tempo e espaço como recursos, análise assintótica) . Tudo estava indo muito bem até que eu acidentalmente admiti que SATpode ser resolvido com eficiência * na prática ... E assim, eu os perdi. Não importava o quão convincentemente eu estivesse tentando argumentar em favor da teoria, o garoto estava convencido de que era tudo matemática de porcaria artificial que ele não deveria cuidar. Bem...

¯ \ _ (ツ) _ / ¯

Não, não fiquei com o coração partido, nem me importei com o que ele pensava, esse não é o objetivo desta pergunta. Nossa conversa me fez pensar em uma pergunta diferente,

Quanto eu realmente sei sobre problemas que são teoricamente intratáveis ​​(complexidade do tempo superpolinomial), mas praticamente solucionáveis ​​(por meio de heurísticas, aproximações, solucionadores de SAT etc.)?

Eu percebi, não muito. Eu sei que existem alguns solucionadores de SAT muito eficientes que resolvem enormes instâncias com eficiência, que o Simplex funciona muito bem na prática e talvez mais alguns problemas ou algoritmos. Você pode me ajudar a pintar uma imagem mais completa? Quais problemas conhecidos ou mesmo classes de problemas estão nessa categoria?

TL; DR: Quais são os problemas que são contra-intuitivamente solucionáveis ​​na prática? Existe um recurso (atualizado) para ler mais? Nós temos uma caracterização para eles? E, finalmente, como uma questão de discussão geral, não deveríamos?

EDIÇÃO 1: Ao tentar responder à minha última pergunta de discussão sobre essa caracterização , fui apresentado à análise suavizada de algoritmos, um conceito introduzido por Daniel Spielman e Shang-Hua Teng em [1] que interpola continuamente entre o pior dos casos e análises de caso médio de algoritmos. Não é exatamente a caracterização discutida acima, mas captura o mesmo conceito, e achei interessante.

Spielman, Daniel A. e Shang-Hua Teng. "Análise suavizada de algoritmos: por que o algoritmo simplex geralmente leva tempo polinomial." Journal of the ACM (JACM) 51, n. 3 (2004): 385-463.

Konstantinos Koiliaris
fonte
6
O que você quis dizer com afirmar que o SAT pode ser resolvido com eficiência na prática? Por que seu amigo confia na segurança da Internet? Presumivelmente, não há problemas difíceis na prática? A robustez é uma das principais vantagens da solvabilidade poli-time / eficiente.
Chandra Chekuri
6
O isomorfismo gráfico é um candidato natural.
DW
2
Ei, @ChandraChekuri, o que eu quis dizer foi que praticamente os solucionadores de SAT podem responder a instâncias de SAT com milhões de variáveis ​​e cláusulas. Ou pelo menos, foi o que pensei que fosse o caso. Não sei ao certo o que você quer dizer com "segurança na Internet"? Não estou argumentando contra o formalismo, estou interessado em problemas que são teoricamente intratáveis, mas para todos os fins práticos (talvez devido a uma aproximação decente, talvez devido à estrutura especial de instâncias do mundo real, etc.) sejam considerados " tratável".
Konstantinos Koiliaris
11
@KonstantinosKoiliaris Acho que o ponto era que a segurança de todos os tipos de protocolos criptográficos depende de (geralmente até algo muito mais forte) e, como tal, fornece muitos exemplos de problemas da prática rotineira que são extremamente difíceis para os solucionadores de SAT ( ou esperamos que sim). PNP
Emil Jeřábek apoia Monica
2
Nesse sentido, pode ser bom verificar a complexidade genérica. De fato, verifica-se que o problema de parada é quase sempre solucionável em tempo polinomial, como é, por exemplo, o SAT (de fato, o SAT tem uma garantia mais forte). O que se entende por "quase sempre" é que o problema admite um algoritmo, de modo que a proporção de entradas para as quais o algoritmo pára (e gera a resposta correta, é claro) em tempo polinomial para 1, à medida que a duração da entrada aumenta.
Guillermo Angeris

Respostas:

17
  • Instâncias SAT altamente estruturadas (mesmo em milhões de variáveis) geralmente podem ser resolvidas na prática. No entanto, instâncias aleatórias de SAT próximas ao limite de satisfação com algumas centenas de variáveis ​​ainda estão abertas (o que significa, mesmo na prática, se você gerar algo que talvez nunca saiba na vida do universo se o que você gerou é satisfatório ou não usando solucionadores SAT atuais). Você pode estar interessado nesta pergunta relacionada e em suas respostas.

  • Os buscadores de cliques também são surpreendentemente bons "na prática"

  • Programação inteira e programação linear inteira mista (com algumas variáveis ​​racionais e algumas inteiras) são o foco de departamentos inteiros de Pesquisa Operacional e podem frequentemente (mas nem sempre) ser resolvidos na prática

  • Pelo que eu entendo, muitos problemas -Complete que surgem na verificação muitas vezes pode ser resolvido na prática, mas "na prática" geralmente implica "em instâncias altamente estruturados". (Por outro lado, ainda não sabemos quem ganha em instâncias bem pequenas do jogo Go, que é outro problema incompleto do P S P A C E. )PSPACEPSPACE

  • EXPSPACE

  • Como já apontado nos comentários da DW, o isomorfismo do gráfico pode ser praticamente resolvido na prática. É muito difícil adotar software GI moderno, como nauty, bliss, picante, etc.

Joshua Grochow
fonte
Obrigado Joshua, estou dando a você os problemas mais interessantes / amplos sugeridos.
Konstantinos Koiliaris
11
Os buscadores de clique nem sempre são bons na prática. Realmente depende do gráfico. E seu link parece estar falando apenas sobre gráficos aleatórios.
Peter Shor
Expandindo um pouco sobre o IG: A maioria dos solucionadores de IG modernos do AFAIK, como os mencionados, usam uma abordagem otimizada de refinamento de individualização (onde o refinamento é o refinamento de cores, que já funciona como um teste de IG quase-linear para quase todos os gráficos) , mas Neuen e Schweitzer recentemente mostraram limites exponenciais inferiores para esse método e construíram (praticamente) instâncias difíceis.
Watercrystal
11
@ JoshuaGrochow: Sim, eu concordo com você sobre isso. Eu só queria expandir a parte "contra-intuitiva" da pergunta, já que o OP mencionou especificamente que o Simplex tem um desempenho muito bom na prática, embora os limites inferiores exponenciais sejam conhecidos e tenhamos a mesma situação aqui.
Watercrystal
11
Eu só tenho experiência com a conjectura de Keller , onde os gráficos (reconhecidamente grandes) surpreenderam muitos algoritmos de busca de cliques.
quer
14

The Hindley-Milner sistema do tipo é usado em linguagens de programação funcional (Haskell, SML, OCaml). O algoritmo de inferência de tipo é quase linear na prática e funciona incrivelmente bem, mas é conhecido por ser DEXPTIME-complete!

Um comentário geral: não é surpresa que a pior complexidade do tempo não seja necessariamente uma medida muito boa do desempenho prático em um algoritmo. No entanto, dizer que a discrepância entre teoria e prática torna a teoria da complexidade inútil é como dizer que os números naturais são um desperdício, porque usamos apenas uma quantidade minúscula de todos os números disponíveis. Um famoso filósofo disse uma vez que "a experiência sem teoria é cega, mas a teoria sem experiência é mero jogo intelectual".

Andrej Bauer
fonte
FPL
6

Mais exemplos, principalmente de linguagens de programação:

  1. O k-CFA (k-Control Flow Analysis) é EXPTIME-complete (Van Horn & Mairson 2008), mas os compiladores de otimização de todo o programa como o MLton o executam de qualquer maneira. Os tempos de compilação são longos, mas raramente desastrosos.
  2. A resolução de sobrecargas (dinâmicas) geralmente é NP-completa (Palsberg 2012). Mas então raramente é um problema no mundo real.
  3. k é o número de registros), que é NP completo. Mas, novamente, raramente é um problema no mundo real.
  4. A solução SMT geralmente é NP-completa, mas os solucionadores comerciais de SMT (como Z3 e CVC4) geralmente têm um bom desempenho. Não trabalho diretamente com os solucionadores SMT, mas usei o Z3 indiretamente da Liquid Haskell e Dafny, e os tempos de verificação parecem bons.
  5. O problema de decisão da aritmética de Presburger é realmente complexo (Fischer & Rabin 1974), mas o algoritmo de decisão de Bill Pugh, o teste Omega (Pugh 1991), geralmente é executado em tempo polinomial de ordem baixa.

Onn


Referências:

[1] David Van Horn e Harry G. Mairson. 2008. Decidir que o kCFA está completo por EXPTIME. Em anais da 13ª Conferência Internacional da ACM SIGPLAN sobre Programação Funcional (ICFP '08). ACM, Nova Iorque, NY, EUA, 275-282.

[2] http://web.cs.ucla.edu/~palsberg/paper/dedicated-to-kozen12.pdf

[3] MJ Fischer e MO Rabin. 1974. COMPLEXIDADE SUPER-EXPONENCIAL DA ARITMÉTICA DE PRESBURGER. Relatório técnico. Instituto de Tecnologia de Massachusetts, Cambridge, MA, EUA.

[4] William Pugh. 1991. O teste Omega: um algoritmo de programação inteiro rápido e prático para análise de dependência. Em Anais da Conferência ACM / IEEE de 1991 sobre Supercomputação (Supercomputing '91). ACM, Nova York, NY, EUA, 4-13.

xrq
fonte
1

também é comprovadamente que o treinamento de redes neurais usando métodos de descida de gradiente é um problema extremamente difícil https://www.cs.utexas.edu/~klivans/crypto-hs.pdf, mas geralmente é solucionável na prática.

riemann77
fonte