Целые точки на эллипсоиде - NP-полная задача

[Ales]

Найти целую точку на эллипсоиде - NP-полная задача.
(Эллипсоид в $\mathbb R^n$ задается уравнением вида: $(x,Ax)+(b,x)+c=0$, матрица $A=A^*$ с положительными собственными значениями, вектор $b$ и число $c$ - целые.)

Получается, что общую проблему можно свести к решению диофантовых уравнений второго порядка, но от многих переменных.

Интересно, можно ли все свести к диофантовому уравнению от двух переменных, пусть более высокого порядка?

-- Чт июн 10, 2010 22:19:37 --

Например к такому $xy=N$?

[Ales]

Чтобы раскусить любой шифр с открытым ключем или найти прообраз для конечного алгоритма, достаточно уметь находить целые решения диофантового уравнени: $(x,Ax)+2(b,x)+c=0$, x \in \mathbb Z^n. $( , )$ - скалярное произведение, $A$ - положительно определенная. Лучше уметь определять: существует ли вообще решение. (Это co-NP полная задача.)

Кто знает как решать такие уравнения, сумеет решить любую разумно поставленную математическую задачу.

Таким образом, центральная проблема математики сводится к исследованию диофантовых уравнений второго порядка от многих переменных.

Изначально вопрос об обратимости алгоритма сводится к уравнению, в котором число переменных, числа, стоящие на главной диагонали матрицы $A$, элементы вектора $b$ и число $c$ - величины порядка числа шагов алгоритма, числа не на главной диагонали $A$ - по модулю 0, 1 или 2.

К сожалению, никак не удается привести $A$ к диагональному виду.

Можно решая уравнение $ax^2+2bxy+cy^2=1, ac-b^2<0$ привести уравнение к системе вида
$\sum \limits _{j=1}^n x_j^2=D y^2 $,
$\sum \limits _{j=1}^n a_j x_j+by=1$. Но толку мало.

А вот привести положительно определенную квадратичную форму к диагональному виду (матрицу $A$) преобразованиями, сохраняющими решетку целых чисел, похоже нельзя.

Предварительный вывод: никак не упростить и не свести к факторизации,
скорее всего задача факторизации не NP-полная.
Ведь для факторизации достаточно решать уравнения второго порядка от двух переменных, хоть и с большими коэффициентами.

[maxal]

Ales в сообщении #331690 писал(а):

скорее всего задача факторизации не NP-полная.

См. topic24200.html

[Ales]

Оказывается (известный результат Adleman, Manders 1978), решение уравнения $ax^2+by=c$ в целых положительных числах - NP-полная задача.
Что может быть проще?
Но это не совсем Диофантово уравнение - есть ограничение y>0, область решений лишена алгебры.

[maxal]

Ales в сообщении #348539 писал(а):

Оказывается (известный результат Adleman, Manders 1978), решение уравнения $ax^2+by=c$ в целых положительных числах - NP-полная задача.
Что может быть проще?
Но это не совсем Диофантово уравнение - есть ограничение y<0, область решений лишена алгебры.

Это несущественное ограничение, так как решений с $y\geq 0$ лишь конечное число (я предполагаю, что $a$ - положительное число).

Кстати, не так давно я решал подобную задачку, когда вычислял новые члены последовательности A094353.

P. S. Статья Adleman и Manders живет тут: http://dx.doi.org/10.1016/0022-0000(78)90044-2

[Ales]

Перепутал: написал сначала $y<0$, надо $y>0$. Потом поправил.

maxal в сообщении #348543 писал(а):

Это несущественное ограничение, так как решений с $y\geq 0$ лишь конечное число (я предполагаю, что $a$ - положительное число).

Нет, это существенно, что в решение в натуральных числах.
Если просто в целых, задача сводится к вопросу является ли $\frac a c$ квадратичным вычетом по модулю $b$. Чтобы ответить на этот вопрос достаточно факторизации.
Тогда бы факторизация была бы полной задачей.

[maxal]

Ales в сообщении #348552 писал(а):

Перепутал: написал сначала $y<0$, надо $y>0$. Потом поправил.

OK. Теперь все встало на свои места.

Но я решал вычислительную задачу (а не задачу распознавания) как раз с отрицательным $y$, но с дополнительным требованием минимальности $x$.