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

37

Задача суммы квадратных корней задает для заданных двух последовательностей a1,a2,,an и b1,b2,,bn натуральных чисел, является ли сумма iai меньше, равно или больше суммы . Статус сложности этой проблемы открыт; см.этот постдля получения дополнительной информации. Эта проблема естественным образом возникает в вычислительной геометрии, особенно в задачах, связанных с евклидовыми кратчайшими путями, и является серьезным камнем преткновения при переносе алгоритмов для этих задач из реальной ОЗУ в стандартную целочисленную ОЗУ.ibi

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

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

Экземпляр: граф , вершинами которого являются точки в Z 4 с ребрами, взвешенными по евклидову дальнему; две вершины s и tG=(V,E)Z4st

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

Конечно, эта проблема может быть решена за полиномиальное время в реальном ОЗУ с использованием алгоритма Дейкстры, но каждое сравнение в этом алгоритме требует решения проблемы суммы квадратов корней. Сокращение использует тот факт, что любое целое число может быть записано как сумма четырех совершенных квадратов; Результатом сокращения является цикл на вершин.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.

Jeffε
источник
1
Thanks to Suresh and Peter for suggesting this question.
Jeffε
8
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 R4 in your shortest-paths problem statement, or Z4? 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ε

Ответы:

21

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 PPPPPPP 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
источник
9
There is also this improvement [mpi-inf.mpg.de/~csaha/Sum_sqrroot.pdf] that puts the problem in CoRPPP and also proves that a restricted version of the problem needs a polynomial number of bits.
Elias
1
@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
1
@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
1
@Tsuyoshi: They solved completely the polynomial version of the problem. Based on this they prove that if ai are of special form, i.e. ai=ibijXdij where X>(B+1)(nd)O(1), B=max{bij} and d=max{di}, then we need a polynomial number of bits to decide the problem.
Elias
3
@Tsuyoshi: I completely misunderstood your question. I am sorry for this. What Kayal and Saha prove is that DegSLP is in CoRPPP. I should be more careful. Thank you for this.
Elias