Сумма квадратов-трудных проблем?

Задача суммы квадратных корней задает для заданных двух последовательностей $a_1, a_2, \dots, a_n$ и $b_1, b_2, \dots, b_n$ натуральных чисел, является ли сумма $\sum_i \sqrt{a_i}$ меньше, равно или больше суммы . Статус сложности этой проблемы открыт; см.этот постдля получения дополнительной информации. Эта проблема естественным образом возникает в вычислительной геометрии, особенно в задачах, связанных с евклидовыми кратчайшими путями, и является серьезным камнем преткновения при переносе алгоритмов для этих задач из реальной ОЗУ в стандартную целочисленную ОЗУ. $\sum_i \sqrt{b_i}$

Назовите задачу Π сумма квадратов-корней-хард (сокращенно Σ√-хард?), Если есть сокращение за полиномиальное время от суммы задачи о квадратных корнях к Π. Нетрудно доказать, что следующая проблема сложна как сумма квадратов:

Кратчайшие пути в 4d евклидовых геометрических графах

Экземпляр: граф , вершинами которого являются точки в с ребрами, взвешенными по евклидову дальнему; две вершины и $G=(V,E)$ $\mathbb{Z}^4$ $s$ $t$

Выход: Самый короткий путь от до в . $s$ $t$ $G$

Конечно, эта проблема может быть решена за полиномиальное время в реальном ОЗУ с использованием алгоритма Дейкстры, но каждое сравнение в этом алгоритме требует решения проблемы суммы квадратов корней. Сокращение использует тот факт, что любое целое число может быть записано как сумма четырех совершенных квадратов; Результатом сокращения является цикл на вершин. $2n+2$

What other problems are sum-of-square-roots-hard? I'm particularly interested in problems for which there is a polynomial-time solution on the real RAM. See my previous question for one possibility.

As Robin suggests, boring answers are boring. For any complexity class X that contains sum-of-square-roots (for example, PSPACE or EXPTIME), every X-hard problem is boringly sum-of-square-roots-hard.

ds.algorithms big-list reductions computing-over-reals Jeffε
источник

Thanks to Suresh and Peter for suggesting this question.

Jeffε

Perhaps you could also rule out trivial answers by insisting that the answers shouldn't just be problems that are hard for a class that's known to contain the Sum-of-square-roots problem. For example, any PSPACE-hard problem would be Sum-of-square-roots-hard, but that's probably not interesting.

Robin Kothari

Do you really mean

R^{4}

$\mathbb{R}^4$ in your shortest-paths problem statement, or

Z^{4}

$\mathbb{Z}^4$ ? The former doesn't seem like it could use an integer RAM at all, and presumably the problem is still Σ√-hard restricting to integer points...

Steven Stadnicki

@Steven: Yup, you're right. Edited.

Jeffε

Ответы:

This was discussed a bit in the following survey (starting slide 21): http://homepages.inf.ed.ac.uk/kousha/games08_tutorial.pdf

which mentions Euclidean TSP, approximation of actual Nash equilibrium, and talks about the classes PosSLP and FIXP.

Noam
источник

this is a fascinating connection.

Suresh Venkat

This should be a comment, as it is a mostly boring answer, but I don´t have enough reputation.

The sum of square roots problem is in $P^{PP^{PP^{PP}}}$ from [ABKM98], so any problem hard for this class has the required property. This is done by reducing the sum-of-square-roots problem to a problem called $PosSLP$ , defined as deciding whether a straight-line problem represents a positive integer, so that problem is sum-of-square-roots hard.

[ABKM98]: On the Complexity of Numerical analysis, by Allender, Burgisser, Kjeldgaard-Pedersen and Miltersen.

Abel Molina
источник

There is also this improvement [mpi-inf.mpg.de/~csaha/Sum_sqrroot.pdf] that puts the problem in

{C o R P}^{P P}

${CoRP}^{PP}$ and also proves that a restricted version of the problem needs a polynomial number of bits.

Elias

@Elias: Can you elaborate? From a cursory look, Kayal and Saha seem to be discussing the “polynomial version” of the sum of square roots problem, which is related to but different from the usual sum of square roots problem.

Tsuyoshi Ito

@Abel: (1) Hi Abel, glad to see your post! (2) For what it’s worth, [ABKM98] was actually presented at CCC 2006 and published in 2009. (3) A boring answer should not be a comment but should be kept to yourself. But I do not think that this is a boring answer. :)

Tsuyoshi Ito

@Tsuyoshi: They solved completely the polynomial version of the problem. Based on this they prove that if

a_{i}

$a_i$ are of special form, i.e.

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

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

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

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

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

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

d = m a x {d_{i}}

$d=max\{d_i\}$ , then we need a polynomial number of bits to decide the problem.

Elias

@Tsuyoshi: I completely misunderstood your question. I am sorry for this. What Kayal and Saha prove is that DegSLP is in

C o R P^{P P}

$CoRP^{PP}$ . I should be more careful. Thank you for this.

Elias