Ganzzahlbeziehungserkennung für Teilmenge Summe oder KKW?

14

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.2N2N

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?

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 S eine Menge positiver Ganzzahlen ist, wobei S ' eine Lösung ist, die 0 = a S ' a erfüllt . Dies ist genau eine lineare Kombination mit reellen Koeffizienten gleich 1. Wenn für jedes a iS gilt : i a i < 2 n -t=0SS0=einSeineinichS Es gibt immer eine Lösung, und die Zuordnung zu einer ganzzahligen Beziehung gibt Ihnen auch eine Lösung. icheinich<2n-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

Antworten:

2

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 Ω ( 2 m ) Zeit. Es ist kein polynomieller Zeitalgorithmus bekannt, wenn m = ω ( log n ) und m = o ( n )m=Ö(Logn)Ω(2m)m=ω(Logn)m=Ö(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
2
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