Czy istnieje równanie P-zupełne w równaniach diofantycznych?

11

Zasadniczo podejmowanie decyzji, czy równanie diofantyczne ma jakieś rozwiązania liczb całkowitych, jest równoznaczne z problemem zatrzymania. Uważam, że podjęcie decyzji, czy kwadratowe równanie diofantyczne ma jakieś rozwiązanie, jest NP-kompletne. Czy istnieje dodatkowe ograniczenie zaangażowanych równań, które powoduje problem z P-zupełnością?

cc.complexity-theory linear-algebra polynomials Jacob Edelman
źródło
1
Myślę, że problem związany z gcd został pokazany jako P.
T ....
3
@ EmilJeřábek Ups, źle podałem wynik. Rozwiązanie musi być pozytywne . Jest wymieniony jako problem A.4.2 w Kompendium problemów ukończonych dla P , technika z 1991 roku. Raport Greenlaw i in.
mhum,
2
@ EmilJeřábek Oczywiście ponad liczbami całkowitymi jest to tylko programowanie liczb całkowitych. Miałem na myśli to, że uczynienie programowania liniowego brzmieniem problemu diofantycznych równań, mówiąc, że chcesz racjonalnego rozwiązania, jest nieco mylące, ponieważ naleganie na racjonalne rozwiązanie nie stanowi żadnego problemu. To znaczy, jeśli zapytasz, czy układ równań liniowych ma rozwiązanie nad rzeczywistością nieujemną, problem byłby dokładnie taki sam.
Sasho Nikolov,
1
@SashoNikolov To nie jest ograniczenie. Bez określenia domeny dla rozwiązań problem jest po prostu źle sformułowany , chyba że domenę można wywnioskować z kontekstu. I tutaj kontekst jest taki, że domniemaną domeną byłyby liczby całkowite, dlatego należy wyraźnie stwierdzić, że jest to coś innego. Tak, tutaj nie ma znaczenia, czy ktoś wybiera racjonalne, realne, czy jakiekolwiek inne pola o charakterystyce 0. Wybór Mhuma, by nazwać go „racjonalnym”, jest równie ważny, jak wybór, by nazwać go „realnym”.
Emil Jeřábek
1
@ EmilJeřábek W większości zgadzam się z tym, co mówisz. W jakiś sposób nie przekazuję tego, że dla mnie programowaniu liniowemu brakuje teoretycznego aspektu problemu równań diofantycznych.
Sasho Nikolov,

Odpowiedzi:

-3

Nie, o ile wiem, problem diafantyny w ogólności jest nierozstrzygalny, a zatem równoważny problemowi zatrzymania, jeśli równania są ograniczone do kwadratyki, to jest np. Kompletne, a liniowe równanie diafantyny można sprowadzić do problemu programowania liczb całkowitych i do liniowego równania diofantyny równania, rozwiązania integralne istnieją wtedy i tylko wtedy, gdy GCD współczynników dwóch zmiennych doskonale dzieli składnik stały.

riemann77
źródło