Ganzzahlbeziehungserkennung für Teilmenge Summe oder KKW?

Gibt es eine Möglichkeit, eine Instanz von Subset Sum oder das Number Partition Problem zu codieren, sodass eine (kleine) Lösung für eine Ganzzahlbeziehung eine Antwort ergibt? Wenn nicht definitiv, dann in einem wahrscheinlichkeitstheoretischen Sinne?

Ich weiß, dass LLL (und möglicherweise PSLQ) mit mäßigem Erfolg bei der Lösung von Subset-Summen-Problemen in der Region mit geringer Dichte eingesetzt wurde, in der der ausgewählte Zahlenbereich größer als , aber diese Methoden lassen sich nicht gut skalieren zu Instanzen größerer Größe und zum Fehlschlagen in der Region 'hoher Dichte', wenn der gewählte Zahlenbereich viel kleiner als . Hier bezieht sich niedrige Dichte und hohe Dichte auf die Anzahl der Lösungen. Der Bereich mit niedriger Dichte bezieht sich auf die wenigen oder gar nicht vorhandenen Lösungen, während sich der Bereich mit hoher Dichte auf einen Bereich mit vielen Lösungen bezieht. $2^N$ $2^N$

In der Region mit hoher Dichte findet LLL (kleine) ganzzahlige Beziehungen zwischen gegebenen Instanzen, aber wenn die Instanzgröße zunimmt, wird die Wahrscheinlichkeit, dass die gefundene Beziehung eine tragfähige Teilmengen- oder Zahlenpartitionsproblemlösung ist, immer kleiner.

Die Erkennung von Ganzzahlbeziehungen ist polynomiell bis in eine exponentielle Grenze des Optimums, wohingegen Teilmenge Summe und NPP offensichtlich NP-vollständig sind. Im Allgemeinen ist dies wahrscheinlich nicht möglich. Könnte dies jedoch einfacher sein, wenn die Instanz gleichmäßig zufällig gezeichnet wird?

Oder sollte ich diese Frage nicht einmal stellen und stattdessen fragen, ob es eine Möglichkeit gibt, die Exponentialgrenze von der optimalen Antwort anstelle einer exponentiellen Zunahme der Berechnung zu verringern?

cc.complexity-theory np-hardness approximation-algorithms reductions subset-sum user834
quelle

Ich habe keine Antworten erhalten, daher habe ich einen Cross-Post an mathoverflow gesendet: mathoverflow.net/questions/38063/…

user834

Dies ist eine sehr interessante Frage, ich warte auch auf Antworten. Sie fordern im Grunde genommen eine (möglicherweise zufällige) Reduzierung der Polynomzeit von der Teilmengen-Summe oder dem KKW auf eine ganzzahlige Beziehung. Wie wäre es damit, wenn

das Ziel Ihres Teilmengen-Summenproblems ist und

eine Menge positiver Ganzzahlen ist, wobei

eine Lösung ist, die

erfüllt . Dies ist genau eine lineare Kombination mit reellen Koeffizienten gleich 1. Wenn für jedes

t = 0

$t=0$

S

$S$

S^{'}

$S'$

0 = \sum_{a \in S^{'}} a

$0=\sum_{a\in S'} a$

a_{i} \in S

$a_i \in S$

Es gibt immer eine Lösung, und die Zuordnung zu einer ganzzahligen Beziehung gibt Ihnen auch eine Lösung.

\sum_{i} a_{i} < 2^{n} - 1

$\sum_i a_i < 2^n-1$

Marcos Villagra

@Marcos Villagra: Dein Kommentar ist etwas schwer zu parsen ... man kann das Problem als Teilmengen-Summen / Zahlen-Partitions-Problem in ein Gitter einbetten (siehe hier für eine Übersicht), die Frage ist einen Weg zu finden, die Koeffizienten auf das zu beschränken gewünschte Menge (z. B. 0,1 oder -1,1). LLL findet eine ganzzahlige Beziehung, auch eine kleine, aber nur eine 2 oder 3 als Koeffizient macht sie als Teilmengen-Summen / Zahlen-Partitionsantwort ungültig.

User834

Sei m der Logarithmus der größten Zahl. Wenn ist, ist es durch dynamische Programmierung in Polynomzeit lösbar. Im Allgemeinen benötigt jeder bekannte Algorithmus mindestens Zeit. Es ist kein polynomieller Zeitalgorithmus bekannt, wenn und $m=O(\log n)$ $\Omega(2^{m})$ $m=\omega(\log n)$ $m=o(n)$

Flaxman und Przydatek stellen jedoch einen Algorithmus zur Verfügung, mit dem Teilmengen-Summenprobleme mittlerer Dichte in der erwarteten Polynomzeit gelöst werden können.

Überprüfen Sie diese Referenz:

Flaxman und Przydatek lösen Teilmengenprobleme mittlerer Dichte in der erwarteten Polynomzeit

Mohammad Al-Turkistany
quelle

Dieses Ergebnis dient nur zur Auswahl der Zahlen in der Subset-Summen-Instanz, die erheblich niedriger sind als ich möchte. Sie wählen den Zahlenbereich in der Reihenfolge log (n) ^ 2, während ich im Zahlenbereich in der Reihenfolge 2 ^ n interessant bin. Es gibt bekannte Algorithmen zum Lösen von Teilmengen, wenn der Bereich der Zahlen auf einen so geringen Wert beschränkt ist und es so aussieht, als hätte man diesen Bereich nur ein wenig erweitert. Das ist großartig, es ist einfach nicht das, wonach ich gesucht habe. Trotzdem danke.

User834

Ganzzahlbeziehungserkennung für Teilmenge Summe oder KKW?

Antworten: