Problemas mais difíceis de otimização na NC

8

Ao aprender problemas de otimização, geralmente consideramos a programação linear (ou mais geralmente: otimização convexa) como o exemplo mais simples. É solucionável em tempo polinomial e possui algoritmos relativamente fáceis de entender. No entanto, a versão de decisão do LP é concluída. Isso sugere que este é um dos problemas mais difíceis que podemos resolver no tempo polinomial. $\mathsf{P}$

Sob a suposição de que . Qual é o tipo natural "mais difícil" de problemas de otimização com problemas de decisão em ? $\mathsf{NC} \neq \mathsf{P}$ $\mathsf{NC}$

Se isso for muito vago, podemos restringir a restrições. Qual é o conjunto mínimo de restrições que precisamos colocar em programas lineares (ou mais geralmente: programas convexos) para permitir que o problema de decisão associado aos programas restritos seja solucionável em ? $\mathsf{NC}$

Motivação

Em grande parte, isso é curiosidade ociosa. No entanto, foi criado por " Na União Soviética, o problema de otimização resolve você ", de Cosma Shalizi . Em particular, se o LP é muito difícil de resolver para ter uma economia centralizada (ou seja, otimizar em está pedindo demais), qualquer sistema descentralizado deve estar executando algum tipo de processamento paralelo mais rapidamente do que o poli-tempo (para mim : ). $\mathsf{P}$ $\mathsf{NC}$

cc.complexity-theory optimization linear-programming Artem Kaznatcheev
fonte

Como o NC é uma hierarquia, é improvável que você encontre um problema "mais difícil" no NC (mais precisamente: o NC não possui problemas completos, a menos que a hierarquia do NC seja reduzida). Da mesma forma, provavelmente não há um conjunto mínimo "universal" de restrições ao PL para colocá-lo na NC, embora isso pareça mais difícil de descartar, mesmo condicionado a suposições naturais. (Isto não é para prejudicar a pergunta - I como a pergunta, e, obviamente, produziu algumas respostas interessantes -. Apenas uma observação)

Joshua Grochow

9

Você está ciente do trabalho em LPs / SDPs positivos? Há vários resultados na área, principalmente na linha de "se as restrições do LP / SDP são positivas, então o problema pode ser resolvido no NC".

Algumas referências importantes nessa linha de trabalho são Luby-Nisan 93 e Jain-Yao 11 . Outro excelente recurso é este slide da palestra de Rahul Jain na conferência "Progressos Recentes em Algoritmos Quânticos" no IQC. A palestra inteira está disponível no youtube.

Robin Kothari
fonte

1

P O

$\mathsf{PO}$

N C

$\mathsf{NC}$

N C

$\mathsf{NC}$

N C O

$\mathsf{NCO}$

P = N C

$\mathsf{P} = \mathsf{NC}$

P

$P$

2

Não tenho certeza, mas você pode estar interessado - se não, desculpe-me - pelo artigo a seguir , que não está relacionado a um tipo natural de problema de otimização, mas lida com um problema que pode ser reduzido a um problema específico de otimização , cuja solução está no NC.

Igor Averbakh, Oded Berman, "Algoritmos NC paralelos para problemas de localização de multifacilidade com comunicação mútua e suas aplicações", Networks, Volume 40, Edição 1, páginas 1–12, agosto de 2002, Wiley

DOI: 10.1002 / net.10027

Resumo

O problema genérico estudado é localizar instalações distintas em uma árvore para satisfazer restrições de limites superiores nas distâncias entre pares de instalações, uma vez que cada instalação deve estar localizada dentro de sua própria região viável, definida como uma subárvore da árvore. Apresentamos um esquema de localização paralela (PLS) para resolver o problema que pode ser implementado como um algoritmo NC. Também introduzimos algoritmos NC paralelos baseados no PLS para as versões minimax do problema, incluindo o problema do centro-p com restrição de distância e comunicação mútua. Combinando o PLS e a técnica paramétrica do Megiddo aprimorada, desenvolvemos algoritmos seriais fortemente polinomiais para os problemas do minimax; os algoritmos têm as melhores complexidades atualmente disponíveis na literatura.

Massimo Cafaro
fonte

Problemas mais difíceis de otimização na NC

Motivação

Respostas: