Problemas que podem ser usados para mostrar resultados de dureza em tempo polinomial

58

Ao projetar um algoritmo para um novo problema, se não conseguir encontrar um algoritmo de tempo polinomial depois de um tempo, talvez eu tente provar que é NP-difícil. Se for bem-sucedido, expliquei por que não consegui encontrar o algoritmo de tempo polinomial. Não é que eu tenha certeza de que P! = NP, é apenas que isso é o melhor que pode ser feito com o conhecimento atual e, de fato, o consenso é que P! = NP.

Da mesma forma, digamos que encontrei uma solução em tempo polinomial para algum problema, mas o tempo de execução é . Depois de muito esforço, não faço progressos para melhorar isso. Então, em vez disso, posso tentar provar que é 3SUM-difícil. Isso geralmente é um estado de coisas satisfatório, não por causa da minha suprema crença de que o 3SUM realmente exige tempo, mas porque esse é o estado da arte atual, e muitas pessoas inteligentes tentaram melhorar e falharam. Portanto, não é minha culpa que seja o melhor que posso fazer. $O(n^2)$ $\Theta(n^2)$

Nesses casos, o melhor que podemos fazer é um resultado de dureza, em vez de um limite inferior real, pois não temos limites inferiores super-lineares para Turing Machines para problemas em NP.

Existe um conjunto uniforme de problemas que pode ser usado para todos os tempos de execução polinomiais? Por exemplo, se eu quiser provar que é improvável que algum problema tenha um algoritmo melhor que , existe algum problema X que eu possa mostrar que é X-difícil e deixar assim? $O(n^7)$

Atualização : Esta pergunta originalmente pedia famílias de problemas. Como não existem muitas famílias de problemas e essa pergunta já recebeu excelentes exemplos de problemas físicos individuais, estou relaxando a questão para qualquer problema que possa ser usado para resultados de dureza em tempo polinomial. Também estou adicionando uma recompensa a esta pergunta para incentivar mais respostas.

cc.complexity-theory lower-bounds conditional-results Robin Kothari
fonte

5

A página maven.smith.edu/~orourke/TOPP/P11.html resume alguns resultados sobre os limites inferiores (e superiores) do 3SUM e problemas relacionados e vale a pena ler.

Tsuyoshi Ito

2

A ausência de limites inferiores super-lineares é para uma MT com pelo menos duas fitas, não é? Lembro-me de ler em algum lugar que a verificação de um palíndromo em uma fita métrica tem um limite inferior em tempo quadrático. Quando falamos de limites inferiores dentro de , do tipo vs. , ainda é aceitável supor que o modelo exato da MT não importa muito?

P

$P$

Ω (n^{i})

$\Omega(n^i)$

Ω (n^{i + 1})

$\Omega(n^{i+1})$

Gphilip # 14/10

3

Fora do tópico: Robin, Tsuyoshi, obrigado por apresentar a família 3SUM de limites inferiores: eu nunca tinha ouvido falar deles antes.

Gphilip # 14/10

2

@ Tsuyoshi: Obrigado pela informação. Esta é uma boa pesquisa sobre o tema: cs.mcgill.ca/~jking/papers/3sumhard.pdf . @ gphilip: Fui apresentado recentemente a esse problema por alguns geômetros computacionais. Eu acho que é muito conhecido nessa área.

Robin Kothari

Ótima pergunta. Você poderia esclarecer o que quer dizer com "uniforme": deseja limitar a quantidade de pré-processamento do parâmetro?

András Salamon

35

Sim, o algoritmo mais conhecido para SUM é executado no tempo , por isso é muito possível que você possa argumentar que algum problema é difícil, porque se estiver em então você pode resolver -SUM mais rápido. $k$ $O(n^{\lceil k/2 \rceil})$ $n^7$ $n^{6.99}$ $14$

Observe que o problema -SUM fica "mais fácil" à medida que aumenta: dado um algoritmo aprimorado para -SUM, é bastante fácil obter um algoritmo aprimorado para -SUM: use todos os pares de números em seu dada a instância -SUM, substituindo cada par pela soma dos dois e procure uma soma de números dentre os que são iguais a . Então, um algoritmo para SUM implica um algoritmo para -SUM. Em outras palavras, um limite inferior apertado para $k$ $k$ $k$ $2k$ $O(n^2)$ $n$ $2k$ $k$ $0$ $O(n^{k/2-\varepsilon})$ $k$ $O(n^{k-2\varepsilon})$ $2k$ $2k$ -SUM é uma suposição mais forte do que um limite inferior apertado para -SUM. $k$

Outro candidato a um problema difícil é o -Clique. Veja minha resposta -Clique para saber mais sobre isso . Se você puder mostrar (por exemplo) que um algoritmo melhor para o seu problema implica em um algoritmo para -clique, seria necessária uma super descoberta para melhorar seu algoritmo. A complexidade parametrizada fornece muitos exemplos de outros problemas como este: -Clique é difícil para a classe e -SUM é difícil para . $k$ $O(\log n)$ $O(n^2)$ $3$ $k$ $W\[1\]$ $k$ $W\[2\]$

Deixe-me avisá-lo que, embora problemas como esse sejam muito convenientes, problemas como SOMA não estão entre os "mais difíceis" em ; por exemplo, é muito improvável que todos os problemas em pode realmente ser reduzido em tempo linear para SUM. Isso ocorre porque o SOM pode ser resolvido com bits de não-determinismo no tempo linear, portanto, se tudo no tempo quadrático puder ser reduzido para SUM, então e outras conseqüências fantásticas resultarão. Mais sobre esse ponto pode ser encontrado no artigo "Qual a dificuldade dos problemas difíceis ?" $3$ $TIME[n^2]$ $TIME[n^2]$ $3$ $3$ $O(\log n)$ $3$ $P \neq NP$ $n^2$ (Em algum momento, "3SUM-hard" foi chamado de " -hard "; este artigo do SIGACT se queixou corretamente desse nome.) $n^2$

Ryan Williams
fonte

4

O único problema que tenho ao usar o k-clique é que o 3-clique é solucionável em . Se fosse o caso que o k-clique parecesse exigir , seria uma ótima família natural para usar.

O (n^{2} .376)

$O(n^2.376)$

Θ (n^{k})

$\Theta(n^k)$

Robin Kothari

Não vejo uma diferença fundamental entre o uso de -SUM e -Clique. -SUM está em para o mesmo . Se você puder mostrar que um algoritmo melhor para o seu problema implica que -Clique está em , isso é uma forte evidência de que um algoritmo melhor para o seu problema será bastante difícil de encontrar.

k

$k$

k

$k$

k

$k$

O (n^{k / 2})

$O(n^{k/2})$

k

$k$

k

$k$

O (n^{k / 2})

$O(n^{k/2})$

Ryan Williams

referência pura, Ryan. Eu tenho vergonha de não saber disso antes, dado o quão popular o 3SUM é na comunidade de geometria. É claro que isso levanta a questão: existem candidatos naturais por serem difíceis?

n^{2}

$n^2$

Suresh Venkat

@ Ryan: Você está certo, eles são os mesmos. Embora, com k-SUM, pelo menos tenhamos evidências em modelos mais fracos de que o limite conjecturado está correto. Não conheço nenhum argumento que sugira que 3-clique não deva ser resolvido mais rapidamente que a multiplicação de matrizes.

Robin Kothari

@ Robin: Eu teria pensado que qualquer família natural de problemas com limites inferiores prováveis , para , seria uma boa resposta. A constante precisa parece menos importante?

n^{f (k)}

$n^{f(k)}$

f (k) = Θ (k)

$f(k) = \Theta(k)$

András Salamon

14

Acredita-se que o problema de caminhos mais curtos de todos os pares (APSP) requer tempo . Reduzir é uma ótima maneira de argumentar que as melhorias baseadas na Multiplicação Rápida de Matrizes (FMM) são improváveis. $\Omega^\star(n^3)$

Mihai
fonte

2

E o diâmetro de um gráfico? Melhor ainda, torne um problema de decisão "O diâmetro é pelo menos k?". Isso tem a vantagem de não ter um limite superlinear óbvio, até onde eu saiba.

Raphael

9

Acredita-se que os melhores algoritmos para o problema de degeneração afim no espaço dimensional sejam executados no tempo . O problema é o seguinte: Dados pontos no espaço tridimensional com coordenadas inteiras, quaisquer pontos estão em um hiperplano comum? $d$ $O(n^d)$ $n$ $d$ $d+1$

O problema de degeneração afim é -SUM difícil. Se ligarmos o limite inferior conjecturado para SUM, obteremos um limite inferior de . A conjectura para a complexidade do problema de degeneração afim é muito mais forte para , no entanto. $(d+1)$ $k$ $\Omega(n^{\lfloor d/2 \rfloor +1})$ $d \geq 3$

J. Erickson, S. Har-Peled e DM Mount, Sobre o Problema do Mínimo Quadrado Mediano, Geometria Discreta e Computacional, 36, 593-607, 2006. http://www.cs.umd.edu/~mount/Papers /dcg06-lms.pdf

J. Erickson e R. Seidel. Limites inferiores melhores na detecção de degenerescências esféricas e finas. Computação Discreta. Geom., 13: 41–57, 1995. http://compgeom.cs.uiuc.edu/~jeffe/pubs/degen.html

J. Erickson. Novos limites inferiores para problemas convexos do casco em dimensões ímpares. SIAM J. Comput., 28: 1198–1214, 1999. http://compgeom.cs.uiuc.edu/~jeffe/pubs/convex.html

Guilherme D. da Fonseca
fonte

Eu gosto desta resposta, mas você poderia explicar? Por que é acreditado?

Aaron Sterling

8

O problema de Hopcroft é conjecturado para exigir tempo : Dado um conjunto de pontos e um conjunto de linhas no plano, existe algum ponto em alguma linha? $\Theta(n^{4/3})$ $n$ $n$

Jeffε
fonte

7

existem problemas não geométricos que se reduzam ao problema de Hopcroft?

Suresh Venkat

Decidi conceder a recompensa a essa resposta porque nunca tinha ouvido falar desse problema antes.

Robin Kothari

Problemas que podem ser usados ​​para mostrar resultados de dureza em tempo polinomial

Respostas:

Problemas que podem ser usados para mostrar resultados de dureza em tempo polinomial