Существует ли P-полная задача о диофантовых уравнениях?

11

В целом решение о том, имеет ли диофантово уравнение какое-либо целочисленное решение, эквивалентно проблеме остановки. Я считаю, что решение о том, имеет ли какое-либо решение квадратное диофантово уравнение, является NP-полным. Существует ли дополнительное ограничение на используемые уравнения, которое приводит к P-полной задаче?

cc.complexity-theory linear-algebra polynomials Джейкоб Эдельман
источник
1
Я думаю, что проблема, связанная с gcd, была показана P завершена.
T ....
3
@ EmilJeřábek Ой, я неправильно указал результат. Решение должно быть в положительных рациональных. Это перечислено как проблема A.4.2 в Компендиуме проблем, выполненных для P , Tech Tech 1991 года. Отчет Greenlaw, et al.
mhum
2
@ EmilJeřábek Конечно, над целыми числами это просто целочисленное программирование. Я имел в виду, что создание линейного программирования звучит как проблема типа диофантовых уравнений, говоря, что вы хотите рационального решения, немного вводит в заблуждение, потому что настаивание на рациональном решении не добавляет ограничений к проблеме. Т.е. если бы вы спросили, есть ли у системы линейных уравнений решение по неотрицательным вещественным значениям, проблема была бы точно такой же.
Сашо Николов
1
@SashoNikolov Это не ограничение. Без указания домена для решения, проблема является просто некорректной , если домен не может быть выведен из контекста. И здесь контекст таков, что подразумеваемая область будет целыми числами, поэтому нужно явно заявить, что это нечто иное. Да, здесь не имеет значения, выбирает ли кто-то рациональное, реальное или любое другое поле характеристики 0. Выбор Мхума назвать его «рациональным» одинаково действителен, так же как ваш выбор назвать его «реальным».
Эмиль Йержабек
1
@ EmilJeřábek Я в основном согласен с тем, что вы говорите. Что-то я не могу передать, так это то, что мне в линейном программировании не хватает теоретико-числового аспекта проблемы диофантовых уравнений.
Сашо Николов

Ответы:

-3

Нет, насколько я знаю, проблема диафорина в общем неразрешима, что эквивалентно задаче остановки, если уравнения ограничены квадратичными, то она np-полная, а линейное уравнение диаферина может быть сведено к задаче целочисленного программирования и для линейного уравнения Диофанта Уравнения, интегральные решения существуют тогда и только тогда, когда ГКД коэффициентов двух переменных делит постоянный член идеально.

riemann77
источник