É uma regra que problemas discretos sejam difíceis de NP e problemas contínuos não?

Na minha formação em ciência da computação, percebo cada vez mais que a maioria dos problemas discretos é NP-completa (pelo menos), enquanto a otimização de problemas contínuos é quase sempre facilmente alcançável, geralmente através de técnicas de gradiente. Existem exceções para isso?

Um exemplo que eu adoro é o problema em que, dados , decidem se:∫ π - π cos ( a 1 z ) cos ( a 2 z ) … cos ( a n z $a_1, a_2, \ldots, a_n \in \mathbb{N}$

A princípio, isso parece um problema contínuo para avaliar essa integral, no entanto, é fácil mostrar que essa integral não é zero se existir uma partição balanceada do conjunto , portanto esse problema integral é realmente NP-completo.$\{a_1, \ldots, a_n\}$

É claro, eu encorajo a brincar com algumas ferramentas numéricas para se convencer de que a maioria (se não todos) dos truques numéricos para avaliar essa integral está fadada ao fracasso quando for grande o suficiente.$n$

Existem muitos problemas contínuos na forma "testar se essa entrada combinatória pode ser realizada como uma estrutura geométrica" ​​que são completas para a teoria existencial dos reais , um análogo contínuo de NP. Em particular, isso implica que esses problemas são difíceis de NP e não polinomialmente solucionáveis. Os exemplos incluem testar se um determinado gráfico é um gráfico de distância unitária, se um determinado gráfico pode ser desenhado no plano com arestas de segmento de linha reta e, no máximo, um determinado número de cruzamentos, ou se um determinado arranjo de pseudolina pode ser esticado para formar uma linha arranjo.

Existem outros problemas contínuos ainda mais difíceis: por exemplo, encontrar um caminho mais curto entre os obstáculos poliédricos em 3d é completo no PSPACE (Canny & Reif, FOCS'87).

Embora isso não responda exatamente à sua pergunta original, é um exemplo (conjectural) de uma espécie de contraponto filosófico: um problema em que a apresentação é discreta, mas toda a dureza vem do aspecto "contínuo" do problema.

O problema é o problema da soma das raízes quadradas : dados dois conjuntos de números inteiros e , é ? (Existem outras formulações, mas essa é a que eu prefiro.) Embora não se saiba ao certo que sejaB = { b 1 , b 2 , ... , b n } Σ m i = 1$A=\{a_1, a_2, \ldots, a_m\}$$B=\{b_1, b_2, \ldots, b_n\}$$\sum_{i=1}^m \sqrt{a_i}\leq\sum_{j=1}^n\sqrt{b_j}$difícil, suspeita-se que possa ser NP-difícil e de fato estar fora dele (existem, como observado nos comentários, excelentes razões para acreditar que não é NP-completo); a única restrição conhecida até o momento é vários níveis acima da hierarquia polinomial. Obviamente, a apresentação desse problema é o mais discreta possível - um conjunto de números inteiros e uma pergunta de sim / não - mas o desafio surge porque, enquanto calcular raízes quadradas com qualquer precisão especificada é um problema fácil, eles podem precisar ser computados precisão alta (potencialmente superpolinomial) para resolver a desigualdade de uma maneira ou de outra. Esse é um problema "discreto" que surge em um número surpreendente de contextos de otimização e ajuda a contribuir para sua própria complexidade.

Problemas discretos geralmente tendem a ser mais difíceis (por exemplo, LP vs. ILP), mas não é a discrição em si que é o problema ... é como as restrições afetam como você pode pesquisar em seu domínio. Por exemplo, você pode pensar que otimizar um polinômio é algo que você pode fazer com eficiência, mas decidir a convexidade dos quáticos (polinômios grau 4) é difícil para o NP .

O que significa que, mesmo que você já tenha o melhor de alguma forma, simplesmente provar que está no melhor já é difícil para o NP.

Embora, para alguns problemas populares, seja de fato verdade, acho que ambas as suposições são - dependendo do que você define como um problema de otimização - não são verdadeiras.

Primeiro, algumas definições: a maioria dos problemas de otimização não faz parte do NP . Por exemplo, para o problema da mochila : não se pode explorar o não-determinismo para construir a bolsa mais valiosa, simples porque os diferentes ramos não-determinísticos não têm memória compartilhada. NP também é definido como "polinomialmente verificável" (verificando um certificado) [1, p. 34]. Nesse caso, o certificado é, por exemplo, uma bolsa : uma cadeia de bits em que, se o i- ésimo bit estiver definido, isso implica que o i- ésimo item faça parte da bolsa. Você pode realmente verificar em tempo polinomial se essa bolsa é mais valiosa do que um determinado limite (essa é a variante de decisão), mas você não pode, tanto quanto sabemos, com base em uma única bolsa (um número polinomial de bolsas), decidir se essa bolsa é a mais valiosa de todas as bolsas possíveis. Essa é uma diferença vital entre, por exemplo, NP e EXP : no EXP , você pode enumerar todas as sacolas possíveis e fazer a contabilidade sobre qual sacola é a melhor.

A variante de decisão dos problemas de otimização é, em alguns casos, parte do NP , é preciso fazer uma distinção clara entre o sabor da maximização e o sabor da decisão . No sabor da decisão, a pergunta é: " Dado um problema de otimização e um limite de utilidade, existe uma solução com um utilitário maior ou igual a esse limite " (ou ligeiramente modificado para um problema de minimização).

Presumo também que por NP você quer dizer a parte (hipotética) de NP que não faz parte do P . Se P = NP , é claro que o NP-completo ainda existe, mas será igual a P (coincide apenas com P para algumas noções de redução, como reduções polinomiais de muitas e uma por @ AndrásSalamon), o que não é tão impressionante ( e reduziria a " lacuna " que você está afirmando na sua pergunta).

Percebo cada vez mais que os problemas mais discretos são NP-completos.

Agora que resolvemos isso: existem muitos problemas de otimização em P : problema de caminho mais curto , problema de fluxo máximo (para capacidades integrais), árvore de abrangência mínima e correspondência máxima . Embora esses problemas possam parecer "triviais para resolver" para você, ainda são problemas de otimização e, em muitos casos, a construção (e a comprovação da correção) não é tão fácil. Portanto, a alegação não contém todos os problemas discretos como NP-completos. Dado que P não é igual a NP , esses problemas não podem ser NP completos .

Além disso, pode-se percorrer a hierarquia polinomial , essa hierarquia fornece uma maneira de construir um problema de decisão que está em , mas, dado um problema de decisão, você pode (quase) sempre construir um problema de otimização que é pelo menos tão difícil ( se a variante de otimização fosse menos difícil, seria possível resolver a variante de decisão chamando a variante de otimização primeiro e depois tomar uma decisão com base no resultado desse algoritmo).$\Sigma^P_i$

Considerando que otimizar problemas contínuos é quase sempre facilmente alcançável.

Um problema contínuo popular que é difícil para NP é a programação quadrática .

Na programação quadrática, procura-se um vetor que:$\vec{x}$

Na verdade, a programação linear também tem sido considerada difícil para NP , mas com heurísticas com desempenho muito bom (o método Simplex ). O algoritmo do Karmarkar é no entanto, em P .

A partir do momento em que o problema de otimização lida com objetos não convexos, em geral será difícil - se não impossível - encontrar um algoritmo eficiente.

Bibliografia

[1] Complexidade Computacional, uma abordagem moderna , Sanjeev Arora e Boaz Barak