Welche Algorithmen gibt es zur Lösung von linearen Systemen mit natürlichen Zahlen?

Ich betrachte das folgende Problem:

Gegeben -dimensionalen Vektoren des natürlichen Zahlen und einiger Eingangsvektor ist eine lineare Kombination der ‚s mit natürlicher Zahl Koeffizienten?$n$$v_1, \ldots, v_m$$u$$u$$v_i$

dh gibt es einige wobei ?$t_1, \ldots, t_m \in \mathbb{N}$$u = t_1 v_1 + \dots + t_m v_m$

Offensichtlich kann die reelle Zahlenversion dieses Problems durch Gaußsche Eliminierung gelöst werden. Ich frage mich, wurde die ganzzahlige Version dieses Problems untersucht? Welche Algorithmen gibt es, um es zu lösen?

Beachten Sie, dass hier natürliche Zahlen verwendet werden, jedoch keine modulare Arithmetik. Dies unterscheidet sich also etwas vom chinesischen Restsatz und solchen Systemen. Es scheint auch mit diophantinischen Gleichungen zu tun zu haben, aber ich frage mich, was in dem Fall getan wurde, in dem nur nicht negative ganze Zahlen berücksichtigt werden. Dies erinnert auch an ein mehrdimensionales Teilmengen-Summen-Problem, das verallgemeinert wurde, um es uns zu ermöglichen, eine beliebige Anzahl von Kopien jedes Vektors zu erstellen. Es scheint auch in Bezug auf die Prüfung , ob ein Element der ist Gitter durch erzeugt , mit der Ausnahme , dass wir hier nur erlauben lineare Kombinationen mit nicht-negativen Koeffizienten.$u$$v_1,\dots,v_m$

Für alle Interessierten ist dies motiviert, indem untersucht wird, ob sich ein Parikh-Vektor in einer linearen Menge befindet, wie im Satz von Parikh .

Insbesondere interessiert mich ein Algorithmus, der das Problem nur mit natürlichen Zahlenoperationen lösen und vermeiden kann, auf die reellen / Gleitkommazahlen einzugehen.

Ihr Problem ist NP-vollständig, durch Reduktion von der Teilmengen-Summe (es ist in NP, da die Tatsache, dass alles nicht negativ ist, die Koeffizienten der Lösung ausreichend gut begrenzt). Wenn eine Instanz der Teilmengen-Summe gegeben ist (gibt es eine Teilmenge von , die zu summiert ?), Konstruieren wir eine Instanz von Ihnen Problem wie folgt. Für jede setzen wir als Vektor mit zwei Einträgen ungleich Null: und und als Vektor mit einem eindeutigen Eintrag ungleich Null . Der Zielvektor ist$S = \{s_1,\ldots,s_n\}, T$$S$$T$$v_1,\ldots,v_{2n},u$$1 \leq i \leq n$$v_i$$v_{i,i} = 1$$v_{i,n+1} = s_i$$v_{n+i}$$v_{n+i,i} = 1$$u=1,\ldots,1,T$. Jede natürliche Kombination von gleich muss genau eine von auswählen und codiert so eine Teilmenge von deren Summe ist der Wert der letzten Komponente.$v_1,\ldots,v_{2n}$$1,\ldots,1,\ast$$v_i,v_{n+i}$$S$