Lineare Diophantingleichung in nicht negativen ganzen Zahlen

Es gibt nur sehr wenige Informationen über das NP-vollständige Problem der Lösung der linearen Diophantingleichung in nicht-negativen ganzen Zahlen. Das heißt, gibt es eine Lösung in nicht-negativen zu der Gleichung , wo alle Konstanten positiv sind? Die einzige bemerkenswerte Erwähnung dieses Problems, von dem ich weiß, ist in Schrijvers $x_1,x_2, ... , x_n$ $a_1 x_1 + a_2 x_2 + ... + a_n x_n = b$ Theorie der linearen und ganzzahligen Programmierung . Und selbst dann ist es eine ziemlich knappe Diskussion.

Daher würde ich mich über Informationen oder Hinweise zu diesem Problem sehr freuen.

Es gibt zwei Fragen, die mich am meisten interessieren:

Ist es stark NP-komplett?
Ist das damit verbundene Problem, die Anzahl der Lösungen zu zählen, # P-hart oder sogar # P-vollständig?

cc.complexity-theory reference-request np-hardness counting-complexity 4evergr8ful
quelle

Dies ist wirklich keine Frage auf Forschungsebene, und ich kann kaum glauben, dass Sie keine weiteren Informationen gefunden haben. Beginnen Sie hier: en.wikipedia.org/wiki/Knapsack_problem

domotorp

Zu 2) gibt es kein bekanntes Beispiel für ein NP-vollständiges Problem, dessen natürliche Zählversion nicht # P-vollständig ist. Möglicherweise ist es einfacher, eine sparsame Reduzierung für Ihr spezielles Problem zu finden, als eine Referenz zu finden. Dieses Papier macht es für die eng verwandte #SubsetSum: crt.umontreal.ca/~gerardo/tsppd-p-complete.pdf

Sasho Nikolov

Darf ich bitte sowohl @domotorp als auch 4evergr8ful um etwas mehr Höflichkeit bitten? Der erste hätte erklären können, wie sich das Rucksackproblem auf solche diophantischen Gleichungen reduziert, von denen er glaubt, dass dies der Fall ist, während 4evergr8ful sich vielleicht abkühlen könnte, zumal er sowohl um Hilfe bittet als auch offensichtlich unerfahren in der Arbeitsweise dieses Forums ist . Aber ich habe auch über das Rucksackproblem nachgedacht, und es ist mir überhaupt nicht klar, dass es sich auf positive Lösungen von Diophantin-Gleichungen reduziert.

Andrej Bauer

OP, wie @Austin bereits erwähnte, funktioniert die gleiche dynamische Programmidee wie für den Rucksack, um Ihr Problem in der Polynomzeit zu lösen, wenn das

polynomisch begrenzt ist. also nein, das problem ist nicht stark np-vollständig. und domotorp hatte einen guten grund, sie auf die wiki-seite für rucksäcke zu verweisen.

a_{i}

$a_i$

Sasho Nikolov

@ 4evergr8ful Klar, ich bin davon ausgegangen, dass du das Zitat umschrieben hast. Das ist ok. Sie haben sie jedoch falsch zitiert, indem Sie "sechs" in "alle" geändert haben. Da G & J Sparsamkeit definiert (dh die Anzahl der Lösungen ist genau gleich), ist es NICHT wahr, dass jede Reduzierung zwischen Problemen in NP sparsam gemacht werden kann, WENN P = Parität-P. Der Grund dafür ist, dass die Standardreduktion von SAT zu NAE-SAT einen Faktor einführt, der eine Potenz von 2 ist. Dies wird erwartet, da SAT für Parity-P vollständig ist, NAE-SAT jedoch einfach ist (es gibt eine offensichtliche Paarung von Zuweisungen, damit die Antwort immer gerade ist = 0).

Tyson Williams

Antworten:

In Bezug auf (1) ist das Problem nicht stark NP-hart, siehe Folgerung 1 hier :

Papadimitriou, CH (1981). Über die Komplexität der Ganzzahlprogrammierung. Journal of the ACM , 28 (4), 765 & ndash; 768.

Bezüglich (2) liegt das Problem offensichtlich in #P, wenn alle Konstanten positiv sind. Es gibt auch eine # P-vollständige Version von SubsetSum, die fast in Ihre Probleminstanz passt, jedoch erfordert, dass das entweder 0 oder 1 ist, siehe hier : $x_i$

Faliszewski, P. und Hemaspaandra, L. (2009). Die Komplexität des Leistungsindexvergleichs. Theoretical Computer Science 410 (1), 101-107.

Ich bin mir ziemlich sicher, dass die von Faliszewski und Hemaspaandra verwendete Konstruktion so angepasst werden kann, dass die Anforderung nicht benötigt wird, und würde daher behaupten, dass das Problem # P-vollständig ist, vorausgesetzt, dass Konstanten in codiert sind binär. $x_i\in \{0,1\}$

Christoph Haase
quelle

Ich bin kein Experte auf diesem Gebiet, aber ich möchte eine konstruktive Diskussion beginnen. Hier ist ein Versuch, der auf der math.stackexchange.com-Frage basiert. Zählen Sie die Anzahl positiver Lösungen für eine lineare diophantine Gleichung . Das Zeug hängt mit Erhart-Polynomen zusammen, von denen ich nichts weiß, und ich denke auch an @ SashoNikolovs Kommentare oben.

Definieren Sie als die Anzahl der nicht negativen Lösungen der Diophantin-Gleichung wobei die Koeffizienten positiv und nicht negativ sind. Wenn ich meine Rekursionen richtig mache, dann haben wir $N(a_1, a_2, \ldots, a_n; b)$

{ein}_{n} x_{n} + {ein}_{n - 1} x_{n - 1} + \dots + {ein}_{1} x_{1} = b,

$a_n x_n + a_{n-1} x_{n-1} + \cdots + a_1 x_1 = b,$

a_{i}

$a_i$

b

$b$

, und

Nun werden die sum ist ein bisschen lang (gemessen an der Länge der Eingabe), aber wir hoffen, eine bessere Methode zu finden, um sie zu berechnen, als sie tatsächlich zu durchlaufen

N ({ein}_{1}; b) = {\begin{cases} 1 & wenn {ein}_{1} ∣ b \\ 0 & Andernfalls \end{cases}

$N(a_1; b) = \begin{cases} 1 & \text{if $a_1 \mid b$} \\\\ 0 & \text{otherwise} \end{cases}$

N ({ein}_{1}, \dots, {ein}_{n + 1}; b) = \sum_{0 \leq k \leq b / {ein}_{n + 1}} N ({ein}_{1}, \dots, {ein}_{n}; b - {ein}_{n + 1} k)

$N(a_1, \ldots, a_{n+1}; b) = \sum_{0 \leq \ k \ \leq b/a_{n+1}} N(a_1, \ldots, a_n; b - a_{n+1} k)$

's. Wir wissen, dass es in

ein Polynom sein wird, aber ich verstehe nicht, wie man das Polynom schnell genug berechnet.

k

$k$

b

$b$

Andrej Bauer
quelle

Lieber Andrej, bei starker NP-Härte messen wir am Wert des Inputs und nicht an dessen Länge. Siehe auch: en.wikipedia.org/wiki/Knapsack_problem#Dynamic_programming

domotorp 13.11.13

@domotorp, ich denke, Andrej befasst sich mit der zweiten Frage zur # P-Vollständigkeit, nicht mit der ersten Frage zur starken NP-Vollständigkeit, die meines Erachtens sehr einfach zu beantworten ist (nein, das Problem ist nicht stark NP) -Komplett). Andrej, ich bin verwirrt, was du hier zeigen willst? Da das Entscheidungsproblem NP-vollständig ist, können Sie nicht hoffen, die Anzahl der Lösungen zu zählen. Hoffen Sie, die Anzahl der Lösungen zu schätzen? Oder haben Sie einen schneller als exponentiellen Zeitalgorithmus?

Sasho Nikolov

Übrigens, ich halte es für wahrscheinlich, dass der Algorithmus in diesem Artikel (ungefähr die Anzahl der Lösungen für den Rucksack durch dynamische Programmierung) an das Problem der diophantinen Gleichung angepasst werden kann: cs.utexas.edu/~klivans/focs11.pdf

Sasho Nikolov

Ich habe noch eine Tatsache über dieses Problem erfahren. Es gibt drei Arten von Menschen: diejenigen, die es das #lineare diophantine Problem nennen, diejenigen, die es das #unbound rucksack Problem nennen, und schließlich diejenigen, die es das denumerante Problem nennen. Und sie scheinen nicht miteinander zu reden.

4evergr8ful