Principais razões pelas quais os problemas estão em P ou BPP

Recentemente, ao conversar com um físico, afirmei que, em minha experiência, quando um problema que parece ingenuamente levar um tempo exponencial acaba não sendo trivialmente em P ou BPP, uma "razão abrangente" pela qual a redução ocorre geralmente pode ser identificada --- e quase sempre, esse motivo pertence a uma lista de uma dúzia ou menos de "suspeitos comuns" (por exemplo: programação dinâmica, álgebra linear ...). No entanto, isso me levou a pensar: podemos realmente escrever uma lista decente de tais razões? Aqui está uma primeira tentativa incompleta de uma:

(0) Caracterização matemática. O problema tem uma caracterização "puramente matemática" não óbvia que, uma vez conhecida, torna imediato que você possa fazer uma pesquisa exaustiva sobre uma lista de possibilidades pol (n). Exemplo: planaridade de grafos, para a qual um algoritmo O (n ⁶ ) segue o teorema de Kuratowski.

(Como "planar" aponta abaixo, este foi um mau exemplo: mesmo depois de conhecer uma caracterização combinatória da planaridade, fornecer um algoritmo de tempo polinomial ainda é bastante trivial. Então, deixe-me substituir um exemplo melhor aqui: que tal , digamos, "dada uma entrada n escrita em binário, calcule quantas cores são necessárias para colorir um mapa arbitrário embutido em uma superfície com n furos." Não é óbvio a priori que isso seja computável (ou mesmo finito!). Mas existe uma fórmula conhecida que fornece a resposta e, uma vez que você conhece a fórmula, é trivial calcular em tempo polinomial. Enquanto isso, "reduz a menores excluídos / teoria de Robertson-Seymour" provavelmente deve ser adicionado como um motivo abrangente separado pelo qual algo pode ser em P.)

Enfim, esse não é especificamente o tipo de situação que mais me interessa.

(1) programação dinâmica. O problema pode ser dividido de uma maneira que permita uma solução recursiva sem explosão exponencial - geralmente porque as restrições a serem satisfeitas são organizadas em uma ordem linear ou outra simples. "Puramente combinatória"; nenhuma estrutura algébrica é necessária. Indiscutivelmente, a acessibilidade dos gráficos (e, portanto, o 2SAT) são casos especiais.

(2) Matroids. O problema tem uma estrutura matróide, permitindo que um algoritmo ganancioso funcione. Exemplos: correspondência, árvore de abrangência mínima.

(3) Álgebra linear. O problema pode ser reduzido para resolver um sistema linear, calcular um determinante, calcular autovalores, etc. É possível argumentar que a maioria dos problemas que envolvem "cancelamentos milagrosos", incluindo aqueles solucionáveis ​​pelo formalismo da caixa de fósforos da Valiant, também caem sob o guarda-chuva algébrico linear.

(4) Convexidade. O problema pode ser expresso como algum tipo de otimização convexa. Programação semi-definida, programação linear e jogos de soma zero são casos especiais comuns (cada vez mais).

(5) Teste de identidade polinomial. O problema pode ser reduzido à verificação de uma identidade polinomial, de modo que o Teorema Fundamental da Álgebra leve a um algoritmo aleatório eficiente - e, em alguns casos, como primalidade, até um algoritmo comprovadamente determinístico.

(6) Cadeia de Markov Monte Carlo. O problema pode ser reduzido à amostragem do resultado de uma caminhada de mistura rápida. (Exemplo: contando aproximadamente combinações perfeitas.)

(7) Algoritmo euclidiano. GCD, frações continuadas ...

Diversos / Não é óbvio exatamente como classificar: Casamento estável, fatoração polinomial, problema de associação para grupos de permutação, vários outros problemas na teoria dos números e na teoria dos grupos, problemas de rede de baixa dimensão ...

Minha pergunta é: quais são as coisas mais importantes que deixei de fora?

Esclarecer:

• Sei que nenhuma lista pode estar completa: seja qual for o número finito de razões que você dê, alguém será capaz de encontrar um problema exótico que esteja em P, mas não por nenhuma dessas razões. Em parte por esse motivo, estou mais interessado em idéias que colocam muitos problemas diferentes, aparentemente não relacionados, em P ou BPP, do que em idéias que funcionam apenas para um problema.

• Também percebo que é subjetivo como dividir as coisas. Por exemplo, os matróides deveriam ser apenas um caso especial de programação dinâmica? A resolubilidade pela pesquisa aprofundada é importante o suficiente para ser sua própria razão, separada da programação dinâmica? Além disso, muitas vezes o mesmo problema pode estar em P por várias razões, dependendo de como você olha para ele: por exemplo, encontrar um valor próprio principal está em P por causa da álgebra linear, mas também porque é um problema de otimização convexo.

Em resumo, não espero um "teorema de classificação" - apenas uma lista que reflita utilmente o que sabemos atualmente sobre algoritmos eficientes. E é por isso que o que mais me interessa são as técnicas para colocar coisas em P ou BPP que tenham ampla aplicabilidade, mas que não se encaixam na lista acima - ou outras idéias para melhorar minha primeira tentativa bruta de melhorar meu interesse pelo mundo. físico.

Algumas classes de gráficos permitem algoritmos de tempo polinomial para problemas difíceis de NP para a classe de todos os gráficos. Por exemplo, para gráficos perfeitos, pode-se encontrar um maior conjunto independente em tempo polinomial (graças a vzn em um comentário por movimentar minha memória). Por meio da construção de um produto, isso também permite uma explicação unificada para vários CSPs aparentemente bastante tratáveis ​​(como aqueles com estrutura em árvore que geralmente são resolvidos por decomposição hierárquica e a restrição Todos-Diferente que geralmente é resolvida por combinação perfeita).

Pode-se argumentar que gráficos perfeitos são "fáceis" porque permitem boas formulações de programação semidefinida dos problemas em questão (e, portanto, se enquadram na álgebra linear e / ou convexidade). No entanto, não tenho certeza de que capte completamente o que está acontecendo.

• András Z. Salamon e Peter G. Jeavons, Restrições perfeitas são tratáveis , CP 2008, LNCS 5202, 524-528. doi: 10.1007 / 978-3-540-85958-1_35

• Meinolf Sellmann, O politopo dos problemas de satisfação de restrições binárias estruturadas em árvore , CPAIOR 2008, LNCS 5015, 367–371. doi: 10.1007 / 978-3-540-68155-7_39

Conforme observado por Gil Kalai, as propriedades dos gráficos que formam classes fechadas menores podem ser definidas por um conjunto finito de menores proibidos (esse é o teorema de Robertson-Seymour ). Outro resultado de Robertson e Seymour é que o teste da presença de um menor pode ser feito em tempo cúbico. Juntos, eles levam a um algoritmo de tempo polinomial para decidir propriedades que são menos fechadas.

• Neil Robertson e PD Seymour, menores de gráfico. XIII. O problema dos caminhos disjuntos , Journal of Combinatorial Theory, Série B 63 (1) 65–110, 1995. doi: 10.1006 / jctb.1995.1006

Um problema com as propriedades de gráfico fechado menor é que elas são "pequenas"; excluir até um menor exclui muitos gráficos. Essa talvez seja uma das razões pelas quais a decomposição estrutural de Robertson-Seymour funciona: existem poucos gráficos restantes suficientes para que eles tenham uma boa estrutura.

• Serguei Norine, Paul Seymour, Robin Thomas e Paul Wollan, Famílias fechadas menores apropriadas são pequenas , Journal of Combinatorial Theory, Série B 96 (5) 754–757, 2006. doi: 10.1016 / j.jctb.2006.01.006 ( pré-impressão )

Uma tentativa de ir além das classes fechadas menores é por meio de classes definidas por subgráficos proibidos ou subgráficos induzidos proibidos.

As propriedades do gráfico definidas por um conjunto finito de subgráficos proibidos ou subgráficos induzidos são decidíveis em tempo polinomial, examinando todos os subgráficos possíveis.

$F$$F$$F$$F$

$F$

$F$$F$$F$$F$

• Maria Chudnovsky e Paul Seymour, Excluindo subgráficos induzidos , Surveys in Combinatorics 2007, 99-119, Cambridge University Press, ISBN 9780521698238. ( pré-impressão )

$F$$F$$F$

Redução de base de rede (algoritmo LLL). Essa é a base para a fatoração polinomial inteira eficiente e alguns algoritmos criptoanalíticos eficientes, como quebra de geradores congruentes lineares e RSA de baixo grau. Em certo sentido, você pode ver o algoritmo euclidiano como um caso especial.

A programação inteira do Lenstra em dimensão delimitada, o algoritmo Lenstra-Lenstra-Lovasz e algoritmos subsequentes relacionados - o algoritmo de Barvinok para o número de soluções inteiras para um problema de IP na dimensão limitada e o algoritmo P de Kannan para o problema de Frobenius / Sylvester podem ser adicionados como uma categoria especial. Um problema em aberto notável aqui é encontrar um algoritmo P para problemas de ordem superior na Hierarquia Presburger.

Outra classe de algoritmo P que vale a pena mencionar são aqueles que o algoritmo P dado ao objeto provou existir por provas aleatórias. Exemplos: algoritmos para aplicações do Lovasz-Local Lemma; versões algorítmicas do resultado da discrepância de Spencer; (de sabor ligeiramente diferente) versões algorítmicas do lema de regularidade de Szemeredi.

Existe um grande e crescente corpo de teoria sobre classes de problemas de satisfação de restrição de modelo fixo que possuem algoritmos de tempo polinomial. Grande parte deste trabalho requer domínio do livro Hobby e MacKenzie , mas, felizmente, para aqueles de nós que estão mais interessados ​​em ciência da computação do que em álgebra universal, algumas partes dessa teoria foram simplificadas o suficiente para serem acessíveis a um público do TCS.

$\Gamma$$S$$T$$\Gamma$$S$$T$

$\Gamma$$k \ge 3$$k$$\Gamma$$(0,0,\dots,0)$$S$$0$$T$

$\Gamma$$\Gamma$$\Gamma$$\Gamma$; na prática, isso significa que a classe de problemas contém todos os subproblemas sucessivamente mais simples considerados por um solucionador de restrições; portanto, o processo de resolução de restrições evita a geração de instâncias intermediárias "difíceis" e a solução de problemas "fáceis".

$\Gamma$$\Gamma$

Os resultados até o momento parecem indicar que deve haver uma espécie de transformação geral de um espaço de estado de acessibilidade subjacente que pode transformar esses problemas em problemas com uma tupla constante em cada relação, como no exemplo acima. (Esta é minha interpretação pessoal da pesquisa em andamento e pode estar completamente errada , dependendo de como a pesquisa em andamento de um algoritmo para álgebras com termos cíclicos se espalhe, por isso me reservo o direito de retroceder isso.) Sabe-se que quando não há Como essa transformação, o problema é NP-completo. A fronteira da conjectura da dicotomia atualmente envolve o fechamento dessa lacuna; veja a lista de problemas em aberto do Workshop de Álgebra e CSPs de 2011 .

Em ambos os casos, isso provavelmente merece uma entrada na lista de Scott.

Uma segunda classe no PTIME permite que técnicas de consistência local sejam aplicadas para remover possíveis soluções, até que uma solução seja encontrada ou nenhuma solução seja possível. Esta é essencialmente uma versão sofisticada da maneira como a maioria das pessoas resolve os problemas do Sudoku. Também não acho que esse motivo esteja na lista de Scott.

$\Gamma$

Por fim, também há muito trabalho empolgante iniciado por Manuel Bodirsky para o caso de domínios infinitos. Alguns dos algoritmos parecem bastante estranhos e podem acabar resultando em mais entradas na lista de Scott.

Eu vejo Chandra aludido a isso, mas acho que a estrutura de um relaxamento de LP (por exemplo, devido à total desimodularidade) é uma forma generalizada de "estrutura" que leva à polinomialidade. É responsável por uma grande classe de algoritmos de tempo poli. Se incluirmos problemas promissores, também será responsável por uma grande classe de algoritmos de aproximação. As classes de razões mais frequentes que não se seguem dos LPs e / ou SDPs são a eliminação gaussiana e a programação dinâmica. É claro que existem outras, como algoritmos holográficos, que não têm explicações simples.