Liste stark NP-harter Probleme mit numerischen Daten

11

Ich suche stark NP-harte Probleme für eine Reduktion. Bisher habe ich folgende Probleme festgestellt:

3-Partitions-Problem
Müllverpackungsproblem
Numerische dreidimensionale Übereinstimmung
TSP
Jedes NP-vollständige Problem ohne numerische Daten, z. B. ZUFRIEDENHEIT, HAMILTONISCHER ZYKLUS, 3-FARBBARKEIT.

Kennt jemand eine Liste stark NP-harter Probleme?

Wenn nicht, bauen wir hier eine. Kennen Sie andere Probleme mit numerischen Daten, die stark NP-hart sind?

Ich interessiere mich besonders für stark NP-harte Probleme bei gewichteten Graphen.

np-hardness big-list hamiltonian-paths Sigal Maon
quelle

5

Machen Sie Ihre Frage in sich geschlossen, indem Sie "stark" definieren.

Tyson Williams

3

Der längste Pfad ist eine Verallgemeinerung des Hamilton-Pfades, daher ist er stark NP-hart.

Michael Lampis

(1) Ist "stark NP" ein Tippfehler für "stark NP-hart"? (2) Ich glaube nicht, dass "wir hier eins machen können".

Tsuyoshi Ito

Regenbogenfärbung scheint hart in der Breite zu sein, vielleicht auch stark NP hart ...?

vzn

3

Hier ist ein stark vollständiges $NP$ Problem (mit den von Ihnen angeforderten numerischen Daten):

Schur Triples Problem :

Eingabe: Liste von 3N verschiedenen positiven ganzen Zahlen

Frage: Gibt es eine Aufteilung der Liste in N Tripel so dass für jedes Tripel ? $(a_i, b_i, c_i)$ $a_i + b_i= c_i$ $i$

Die Bedingung , dass alle Zahlen müssen verschieden macht das Problem sehr interessant und McDiarmid nennt es eine überraschend mühsam .

Mohammad Al-Turkistany
quelle

0

Während ich über mögliche Antworten nachdachte, kam ich auf dieses einfache numerische, stark NP-vollständige Problem:

QUADRATISCHES UNTERGRUNDPRODUKT: Bei ganzen Zahlen finden Sie von ihnen, deren Produkt quadratfrei ist. $3N$ $N$

$3|X|$ $(x,y,z)$ $xyz$

Ich habe es nirgendwo gefunden, daher kann es etwas "originell" sein.

$B$

Es kann auch ein wenig gehackt werden, um andere Varianten zu erhalten, wie:

$3N$ $N$ $21$
$N$

Marzio De Biasi
quelle

@domotorp: Ich habe die Frage gelöscht. Ich kopiere / füge hier Ihren Kommentar zur Umwandlung der Einschränkung in "... finde eine Teilmenge, deren Produkt eine quadratfreie Zahl größer als M ist ...": "Bedenken Sie zunächst, dass Sie jede Zahl multiplizieren durch eine andere, sehr große Primzahl, so dass alle diese ungefähr gleich groß sind. Dann würde die Auswahl von N Zahlen gleichbedeutend mit der Erzielung eines großen Produkts sein. Wir können (noch) keine großen Primzahlen in P erzeugen, aber tatsächlich brauchen wir keine sie - anstelle jeder Primzahl können wir relative quadratfreie Primzahlen verwenden, und diejenigen, die wir durch Berechnung der ersten polynomiell vielen Primzahlen erzeugen können

Marzio De Biasi

0

$k= \Omega(n)$ $NP$

Mohammad Al-Turkistany
quelle

0

$NP$ $P||C_{max}$

$NP$ $3$

Hoffe das hilft!

Seitenassistent
quelle

Liste stark NP-harter Probleme mit numerischen Daten

Antworten: