Y a-t-il un problème P-complet sur les équations diophantiennes?

11

En général, décider si une équation diophantienne a des solutions entières équivaut au problème d'arrêt. Je crois que décider si une équation diophantienne quadratique a une solution est NP-complet. Existe-t-il une restriction supplémentaire sur les équations impliquées qui génère un problème de P-complet?

cc.complexity-theory linear-algebra polynomials Jacob Edelman
la source
1
Je pense qu'un problème lié à gcd a été montré P complet.
T ....
3
@ EmilJeřábek Oups, j'ai mal dit le résultat. La solution doit être dans les logiques positives . Il est répertorié comme problème A.4.2 dans un recueil de problèmes complets pour P , un technicien de 1991. Rapport de Greenlaw, et al.
mhum
2
@ EmilJeřábek Bien sûr, sur les entiers, ce n'est qu'une programmation entière. Ce que je voulais dire, c'est que faire en sorte que la programmation linéaire sonne comme un problème de type équations diophantiennes en disant que vous voulez une solution rationnelle est un peu trompeur car insister sur une solution rationnelle n'ajoute aucune contrainte au problème. Autrement dit, si vous demandiez si le système d'équations linéaires avait une solution sur les réels non négatifs, le problème serait exactement le même.
Sasho Nikolov
1
@SashoNikolov Ce n'est pas une contrainte. Sans spécifier le domaine des solutions, le problème est simplement mal formé , à moins que le domaine ne puisse être déduit du contexte. Et ici, le contexte est tel que le domaine impliqué serait les entiers, d'où la nécessité de déclarer explicitement qu'il s'agit de quelque chose de différent. Oui, ici, peu importe que l'on choisisse les rationnels, les réels ou tout autre champ de caractéristique 0. Le choix de Mhum de l'appeler "rationnel" est tout aussi valable que votre choix de l'appeler "réel".
Emil Jeřábek
1
@ EmilJeřábek Je suis principalement d'accord avec ce que vous dites. Ce que je ne parviens pas à dire, c'est que pour moi, la programmation linéaire n'a pas l'aspect théorique des nombres du problème des équations diophantiennes.
Sasho Nikolov

Réponses:

-3

Non, pour autant que je sache, le problème diaphantine en général est indécidable, ce qui équivaut à arrêter le problème, si les équations sont restreintes à être quadratiques, alors il est np-complet, et l'équation diaphantine linéaire peut être réduite à un problème de programmation entier et pour l'équation diophantienne linéaire équations, des solutions intégrales existent si et seulement si, le GCD des coefficients des deux variables divise parfaitement le terme constant.

riemann77
la source