Quels algorithmes existent pour résoudre les systèmes linéaires de nombres naturels?

9

Je regarde le problème suivant:

Étant donné les vecteurs à dimensions des nombres naturels v 1 , , v m et un vecteur d'entrée u , u est-il une combinaison linéaire des v i avec des coefficients de nombres naturels?nv1,,vmuuvi

c'est-à-dire qu'il y a u = t 1 v 1 + + t m v m ?t1,,tmNu=t1v1++tmvm

Évidemment, la version en nombre réel de ce problème peut être résolue en utilisant l'élimination gaussienne. Je me demande, la version entière de ce problème a-t-elle été étudiée? Quels algorithmes existent pour le résoudre?

Notez que cela utilise des nombres naturels, mais pas l'arithmétique modulaire, donc c'est quelque peu distinct du théorème des restes chinois et des systèmes comme ça. En outre, cela semble lié aux équations diophantiennes, mais je me demande ce qui a été fait dans le cas où seuls les entiers non négatifs sont pris en compte? Cela rappelle également un problème de sous-ensemble multidimensionnel, généralisé pour nous permettre de prendre un nombre arbitraire de copies de chaque vecteur. Il semble également lié au test pour savoir si est un élément du réseau généré par v 1 , , v m , sauf que nous n'autorisons ici que des combinaisons linéaires avec des coefficients non négatifs.uv1,,vm

Pour toute personne intéressée, cela est motivé par la recherche d'un vecteur Parikh dans un ensemble linéaire, comme dans le théorème de Parikh .

En particulier, je suis intéressé par un algorithme qui pourrait résoudre le problème en utilisant uniquement des opérations de nombres naturels, en évitant d'entrer dans les nombres réels / à virgule flottante.

jmite
la source
2
Oui, la version entière (et différentes versions de la théorie des anneaux) ont été étudiées. La version entière peut être résolue par élimination gaussienne. La version en nombre naturel est une bête différente. Mon sentiment est qu'il devrait être NP-complet.
Thomas Klimpel
Comment peut-il être NP-complet s'il est résolu par élimination gaussienne? Je suis toujours intéressé par les algorithmes pour cela, même si c'est un problème insoluble.
jmite
m<n

Réponses:

9

S={s1,,sn},TSTv1,,v2n,u1invivi,i=1vi,n+1=sivn+ivn+i,i=1u=1,,1,Tv1,,v2n1,,1,vi,vn+iS

Yuval Filmus
la source
Intéressant. Avez-vous trouvé cette preuve ou avez-vous une référence que je pourrais citer? Quoi qu'il en soit, merci!
jmite
1
@jmite Je viens de trouver la preuve, mais je ne peux pas exclure de l'avoir vue.
Yuval Filmus