Задача о сумме квадратного корня

Нерешенная задача в информатике :

Какова сложность задачи о сумме квадратного корня во время выполнения по Тьюрингу?

(еще нерешенные проблемы по информатике)

Задача о сумме квадратного корня (SRS) — это задача вычислительного решения из области численного анализа с приложениями к вычислительной геометрии .

Определения

SRS определяется следующим образом:

Даны положительные целые числа $a_{1},\ldots ,a_{k}$ и целое число t , решите, будет ли $\sum _{i=1}^{k}{\sqrt {a_{i}}}\leq t$.

Альтернативное определение:

Даны положительные целые числа $a_{1},\ldots ,a_{k}$ и $b_{1},\ldots ,b_{k}$, решить, стоит ли $\sum _{i=1}^{k}{\sqrt {a_{i}}}\leq \sum _{i=1}^{k}{\sqrt {b_{i}}}$.

Задача была поставлена ​​в 1981 г. и, вероятно, раньше.

Сложность во время выполнения

SRS может быть решена за полиномиальное время в модели Real RAM . Однако по состоянию на 1997 год сложность его выполнения в модели машины Тьюринга открыта. Основная трудность состоит в том, что для решения задачи необходимо вычислить квадратные корни с высокой точностью, что может потребовать большого количества бит. Проблема упоминается в Саду открытых проблем.

Блумер с полиномиальным временем представляет алгоритм Монте-Карло для определения того, равна ли сумма квадратных корней 0.

Аллендер, Бургиссер, Педерсен и Мильтерсен докажите, что SRS находится в иерархии подсчета (которая содержится в PSPACE ).

Границы разделения

Один из способов решения SRS — доказать нижнюю границу абсолютной разности. $\left|t-\sum _{i=1}^{k}{\sqrt {a_{i}}}\right|$ или $\left|\sum _{i=1}^{k}{\sqrt {a_{i}}}-\sum _{i=1}^{k}{\sqrt {b_{i}}}\right|$. Такая нижняя граница называется «границей разделения», поскольку она отделяет разницу от 0. Например, если абсолютная разница составляет не менее 2 ^{- д} , это означает, что мы можем округлить все числа до d бит точности и решить SRS за полиномиальное от d время .

Это приводит к математической проблеме доказательства границ этой разности. Определите r ( n , k ) как наименьшее положительное значение разности $\sum _{i=1}^{k}{\sqrt {a_{i}}}-\sum _{i=1}^{k}{\sqrt {b_{i}}}$, где a _i и b _i — целые числа от 1 до n ; define R ( n , k ) определяется как -log r ( n , k ), что является количеством цифр точности, необходимых для решения SRS. Вычисление r ( n , k ) — это открытая задача 33 в проекте открытых задач.

В частности, интересно, находится ли r( n , k ) в O(poly( k ,log( n )). Положительный ответ будет означать, что SRS может быть решена за полиномиальное время в модели машины Тьюринга. Некоторые известные в настоящее время границы являются:

• Цянь и Ван докажите явной конструкцией, что для k и n любых $r(n,k)\in O(n^{-2k+3/2})$, так $R(n,k)\geq (2k-3/2)\cdot \log {n}$. Это число является оптимальным при k =2, а также для широкого диапазона целых чисел.
• Бурникель, Фляйшер, Мельхорн и Ширра доказал верхнюю границу количества цифр: $R(n,k)\in O(2^{2k}\cdot \log {n})$.
• Ченг, Мэн, Сунь и Чен показал, что $R(n,k)\in 2^{O(n/\log {n})}\cdot \log {n}$.
• Ченг и Ли показал, что $R(n,k)\in 2^{O(n/\log {n})}$. Это означает, что СРС может быть решена во времени. $2^{o(k)}\cdot (\log {n})^{O(1)}$, пока n находится в o( k log k ). Они также представляют алгоритм для вычисления r ( n , k ) за время. $n^{k+o(k)}$.
• Эйзенбранд, Хеберле и Зингер доказать, что $r(n,k)\geq \gamma \cdot n^{-2n}$, где гамма — константа, зависящая от входных данных a ₁ ,..., an _n и шагов из теоремы о подпространстве . Это улучшает предыдущую оценку $r(n,k)\geq \left(n\cdot \max _{i}({\sqrt {a_{i}}})\right)^{-2^{n}}$.

Приложения

SRS важен в вычислительной геометрии , поскольку евклидовы расстояния задаются квадратными корнями, и многие геометрические задачи (например, минимальное остовное дерево на плоскости и евклидова задача коммивояжера ) требуют вычисления сумм расстояний.

Этессами и Яннакакис показать сведение от СТО к проблеме прекращения рекурсивных параллельных стохастических игр .

Связь с полуопределенным программированием

SRS также имеет теоретическое значение, поскольку представляет собой простой частный случай проблемы осуществимости полуопределенного программирования . Рассмотрим матрицу $\left({\begin{matrix}1&x\\x&a\end{matrix}}\right)$. Эта матрица является положительно полуопределенной тогда и только тогда, когда $a-x^{2}\geq 0$, если $|x|\leq {\sqrt {a}}$. Следовательно, для решения SRS мы можем построить задачу осуществимости с n ограничениями вида $\left({\begin{matrix}1&x_{i}\\x_{i}&a_{i}\end{matrix}}\right)\succeq 0$и дополнительные линейные ограничения $x_{i}\geq 0,\sum _{i=1}^{n}x_{i}\geq k$. Результирующая SDP осуществима тогда и только тогда, когда осуществима SRS. Поскольку сложность выполнения SRS в модели машины Тьюринга открыта, то же самое справедливо и для осуществимости SDP (по состоянию на 1997 год).

Расширения

Каял и Саха расширить задачу от целых чисел до многочленов . Их результаты подразумевают решение СКР для специального класса целых чисел.