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

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. $a_1, a_2, \dots, a_n$ $b_1, b_2, \dots, b_n$ $\sum_i \sqrt{a_i}$ $\sum_i \sqrt{b_i}$

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 e $G=(V,E)$ $\mathbb{Z}^4$ $s$ $t$

Saída: O caminho mais curto de a em . $s$ $t$ $G$

É 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.

ds.algorithms big-list reductions computing-over-reals Jeffε
fonte

Agradecemos a Suresh e Peter por sugerirem esta pergunta.

Jeffε

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

? O primeiro não parece que poderia usar uma RAM inteira, e provavelmente o problema ainda é difícil de restringir a pontos inteiros ...

R^{4}

$\mathbb{R}^4$

Z^{4}

$\mathbb{Z}^4$

Steven Stadnicki

@ Steven: Sim, você está certo. Editado.

Jeffε

Respostas:

Isso foi discutido um pouco na pesquisa a seguir (início do slide 21): http://homepages.inf.ed.ac.uk/kousha/games08_tutorial.pdf

que menciona TSP euclidiano, aproximação do equilíbrio real de Nash, e fala sobre as classes PosSLP e FIXP.

Noam
fonte

essa é uma conexão fascinante.

Suresh Venkat

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^{PP^{PP^{PP}}}$ $PosSLP$

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

Abel Molina
fonte

{C o R P}^{P P}

${CoRP}^{PP}$

@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

@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

a_{i}

$a_i$

a_{i} = \sum_{i} b_{i} j X^{d_{i} - j}

$a_i=\sum_i{b_ij}X^{d_i-j}$

X > (B + 1)^{(n d)^{O (1)}}

$X>(B+1)^{(nd)^{O(1)}}$

B = m a x {b_{i j}}

$B=max\{b_{ij}\}$

d = m a x {d_{i}}

$d=max\{d_i\}$

C o R P^{P P}

$CoRP^{PP}$