Problemas difíceis de soma quadrada de raízes?

37

O problema da soma das raízes quadradas pergunta, dadas duas seqüências e de números inteiros positivos, se a soma menor ou igual a ou maior que a soma . O status de complexidade desse problema está aberto; veja este post para mais detalhes. Esse problema surge naturalmente na geometria computacional, especialmente nos problemas que envolvem os caminhos mais curtos euclidianos, e é um obstáculo significativo na transferência de algoritmos para esses problemas da RAM real para a RAM inteira padrão.b 1 , b 2 , , b n i a1,a2,,anb1,b2,,bniiaiibi

Chame um problema de Π soma das raízes quadradas de disco rígido (abreviado Σ√-disco?) Se houver uma redução no tempo polinomial da soma do problema de raízes quadradas para Π. Não é difícil provar que o seguinte problema é difícil de soma quadrada de raízes:

Caminhos mais curtos nos gráficos 4d geométricos euclidianos

Instância: Um gráfico cujos vértices são pontos em , com arestas ponderadas pelo distano euclidiano; dois vértices eZ 4 s tG=(V,E)Z4st

Saída: O caminho mais curto de a em .t GstG

É claro que esse problema pode ser resolvido em tempo polinomial na RAM real usando o algoritmo de Dijkstra, mas cada comparação nesse algoritmo requer a solução de um problema de soma das raízes quadradas. A redução usa o fato de que qualquer número inteiro pode ser escrito como a soma de quatro quadrados perfeitos; a saída da redução é na verdade um ciclo em vértices.2n+2

Que outros problemas são difíceis de soma quadrada? Estou particularmente interessado em problemas para os quais existe uma solução em tempo polinomial na RAM real. Veja minha pergunta anterior para uma possibilidade.

Como Robin sugere, respostas chatas são chatas. Para qualquer classe de complexidade X que contenha soma quadrada de raízes (por exemplo, PSPACE ou EXPTIME), todo problema X-hard é chato a soma quadrada de raízes quadradas.

Jeffε
fonte
11
Agradecemos a Suresh e Peter por sugerirem esta pergunta.
Jeffε
8
Talvez você também possa descartar respostas triviais insistindo que as respostas não devem ser apenas problemas difíceis para uma classe conhecida por conter o problema da soma das raízes quadradas. Por exemplo, qualquer problema difícil do PSPACE seria difícil de soma quadrada, mas isso provavelmente não é interessante.
Robin Kothari 01/01
Você realmente média em sua declaração do problema mais curtos-caminhos, ou Z 4 ? O primeiro não parece que poderia usar uma RAM inteira, e provavelmente o problema ainda é difícil de restringir a pontos inteiros ...R4Z4
Steven Stadnicki
@ Steven: Sim, você está certo. Editado.
Jeffε

Respostas:

21

Isso deve ser um comentário, já que é uma resposta muito chata, mas não tenho reputação suficiente.

O problema da soma das raízes quadradas está em de [ABKM98] , portanto, qualquer problema difícil para essa classe tem a propriedade necessária. Isso é feito reduzindo o problema da soma das raízes quadradas a um problema chamado , definido como decidir se um problema em linha reta representa um número inteiro positivo, para que o problema seja difícil da soma das raízes quadradas. P o s S G PPPPPPPPPosSLP

[ABKM98]: Sobre a complexidade da análise numérica, de Allender, Burgisser, Kjeldgaard-Pedersen e Miltersen.

Abel Molina
fonte
9
CoRPPP
11
@Elias: Você pode elaborar? Do ponto de vista superficial, Kayal e Saha parecem estar discutindo a "versão polinomial" do problema da soma das raízes quadradas, que está relacionada a, mas diferente da usual, problema da soma das raízes quadradas.
Tsuyoshi Ito
11
@Abel: (1) Oi Abel, feliz em ver seu post! (2) Pelo que vale a pena, [ABKM98] foi realmente apresentado no CCC 2006 e publicado em 2009 . (3) Uma resposta chata não deve ser um comentário, mas deve ser mantida em sigilo. Mas não acho que essa seja uma resposta chata. :)
Tsuyoshi Ito
11
aiai=ibijXdijX>(B+1)(nd)O(1)B=max{bij}d=max{di}
3
CoRPPP