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

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.

• 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"

  • Com relação aos buscadores de cliques, (parte da) explicação é dada por uma análise de caso médio dos algoritmos em questão.

    Consulte https://www.sciencedirect.com/science/article/pii/S0166218X18300167?via%3Dihub

• 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. )$\mathsf{PSPACE}$$\mathsf{PSPACE}$

• $\mathsf{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.

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".

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.

$O$$n$$n$

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.

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.