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

9

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?nv1,,vmuuvi

dh gibt es einige wobei ?t1,,tmNu=t1v1++tmvm

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.uv1,,vm

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.

jmite
quelle
2
Ja, die Ganzzahlversion (und verschiedene ringtheoretische Versionen) wurden untersucht. Die ganzzahlige Version kann durch Gaußsche Eliminierung gelöst werden. Die natürliche Zahlenversion ist ein anderes Tier. Mein Gefühl ist, dass es NP-vollständig sein sollte.
Thomas Klimpel
Wie kann es NP-vollständig sein, wenn es durch Gaußsche Eliminierung gelöst wird? Ich bin immer noch an Algorithmen dafür interessiert, auch wenn es ein unlösbares Problem ist.
Jmite
Beachten Sie auch, dass in dem Problem, das ich betrachte, das System möglicherweise unterbestimmt ist, dh . Ich bin mir nicht sicher, wie sich das ändert. m<n
Jmite

Antworten:

9

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 istS={s1,,sn},TSTv1,,v2n,u1invivi,i=1vi,n+1=sivn+ivn+i,i=1u=1,,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.v1,,v2n1,,1,vi,vn+iS

Yuval Filmus
quelle
Interessant. Haben Sie diesen Beweis erbracht oder haben Sie eine Referenz dafür, die ich zitieren könnte? Wie auch immer, danke!
Jmite
1
@jmite Ich habe mir gerade den Beweis ausgedacht, obwohl ich nicht ausschließen kann, ihn gesehen zu haben.
Yuval Filmus