NP-Härtebeweis: Suche nach guten, eingeschränkten np-harten Problemen

8

Um die NP-Härte eines Problems zu zeigen, muss man ein bekanntes NP-hartes Problem auswählen und eine Polynomreduktion vom bekannten Problem zu seinem vorliegenden Problem finden. Theoretisch kann jedes NP-harte Problem für die Reduktion verwendet werden, aber in der Praxis lassen sich einige der Probleme leichter reduzieren als andere.

Zum Beispiel ist 3-SAT normalerweise eine bessere Wahl für die Erstellung einer Reduktion als SAT, da das erstere eingeschränkter ist als das letztere. 3-Partitionen sind normalerweise eine einfachere Wahl als das Packen von Behältern, ...

Eine Möglichkeit, solche "guten" Probleme für die Reduzierung zu finden, besteht darin, eine statistische Analyse der vorhandenen Reduktionen durchzuführen. Beispielsweise kann man alle from -> toReduktionspaare des Buches Computer und Intraktabilität: Ein Leitfaden zur Theorie der NP-Vollständigkeit (oder anderer Ressourcen) formen und ein Histogramm der Probleme in der fromMenge zeichnen . Dann können wir herausfinden, welche Probleme häufiger für Reduzierungen verwendet werden.

Ich frage mich, ob eine solche statistische Analyse überhaupt Sinn macht. Wurde eine solche Untersuchung bereits durchgeführt oder nicht? Wenn nicht, wie schätzen Sie die am häufigsten verwendeten Probleme bei Reduzierungen ein?

Der Grund, warum ich diese Frage stelle, ist, dass ich bereits einige Beweise für die NP-Härte gemacht habe, aber fast alle von ihnen basieren auf der Reduzierung des gleichen Problems (3-Partition). Ich suche nach anderen Optionen für meine Proofs.

np-hardness reductions Helium
quelle
1
Aus meiner kleinen Erfahrung denke ich, dass es von der Domäne des Problems abhängt, mit dem Sie konfrontiert sind (Arithmetik, Graphentheorie, Zeitplanung, Rätsel, ..); Zunächst sollten Sie nach ähnlichen oder verwandten NPC-Problemen suchen, um festzustellen, ob es ein gutes Problem beim Starten von FROM gibt (z. B. A1-A12-Klassifikation von G & J). Schauen Sie sich dann die NPC-Beweise an, um Hinweise / Einblicke in die Richtung zu erhalten, der Sie folgen können. Wenn nichts herauskommt, versuchen Sie schließlich, einfache "Low-Level" -NPC-Probleme zu verwenden, die keine komplexen Strukturen erfordern (3SAT, 1: 3-SAT, planares SAT, exakte Abdeckung durch drei Sätze, 3-Farben, 3-Partitionen, Ham-Zyklus in planaren oder Gittergraphen, ..)
Marzio De Biasi
@MarzioDeBiasi: Sie haben Recht, aber ich denke, es ist eine anstrengende Aufgabe, unter Tausenden von Problemen nach dem richtigen zu suchen. Das Ranking basierend auf der Anzahl der von mir vorgeschlagenen Reduzierungen gibt uns einen Hinweis darauf, wo wir unsere Suche beginnen sollen. Tatsächlich wählen wir ein Problem normalerweise nicht zufällig aus. Wir wählen das Problem normalerweise basierend auf Ähnlichkeit (ist das ein gutes Wort?) Und basierend auf der Häufigkeit von Reduzierungen, die wir bereits bei diesem Problem gesehen haben. Ich wollte diese Auswahl nur ein bisschen formeller gestalten oder zumindest einige Ratschläge von Experten auf dem Gebiet zu ihren Lieblingsproblemen erhalten.
Helium
@MarzioDeBiasi: Übrigens ist die Liste der Probleme, die Sie in Ihrem Kommentar erwähnt haben, auch für mich nützlich.
Helium
1
@MarzioDeBiasi, ich finde es sehr schön, wenn Sie Ihre Erfahrungen als Antwort teilen, Sie sind einer der Besten in Bezug auf Härteprüfungen in cstheory.SE.
Saeed
1
Hören Sie sich MDB re G & J genau an. Sie organisieren Problemtypen in Abschnitte. Es gibt vielleicht Tausende von vollständigen NP-Problemvarianten, aber sie befinden sich in grundlegenden Themen / Genres / Abschnitten. Ein großer Graph wäre interessant zu konstruieren, aber nicht wirklich statistisch. Es zeigt wahrscheinlich eine kleine Weltstruktur, in der es wichtige "Hubs" gibt. G & J selbst listet die primären Hubs in verschiedenen Kapiteln / Abschnitten auf.
VZN

Antworten:

6

Ich weiß nicht, ob es einen maschinellen Weg gibt, dies zu tun, aber meine kleine persönliche Erfahrung funktioniert wie folgt.

Ich versuche, einen Polynomzeitalgorithmus für ein Problem bereitzustellen. Bei diesen Versuchen kann ich normalerweise sehen, dass es einige eingeschränkte Versionen von Problemen gibt, die polynomial zeitlösbar sind. Ich werde auch verstehen, welcher Teil meines Algorithmus für das ursprüngliche Problem von Hand gewinkt hat. Ich kann diese beiden Fälle vergleichen (Unterschied zwischen eingeschränkten Versionen und der allgemeinen auch der Teil eines Algorithmus, der schwer zu verbessern war). Wenn man diese beiden Fälle normalerweise vergleicht, kann man erraten, wie der Problemengpass aussieht. So können wir ein damit verbundenes schwieriges Problem finden. Normalerweise ist die Bereitstellung eines Algorithmus für ein Problem eine schwierige Aufgabe und erfordert gute Kenntnisse über ein Problem. Nachdem wir dieses Wissen über das Problem erhalten haben, können wir viele verschiedene Ideen haben, um das Problem in verschiedenen Szenarien anzugehen (nicht nur die Ergebnisse der Härte).

PS: Wenn sich Ihr Beweis auf ein bestimmtes Problem bezieht, liegt das meiner Meinung nach daran, dass dieses Problem Ihrer Arbeit sehr nahe kommt. Machen Sie sich also keine Vorwürfe.

Saeed
quelle
2
+1: Ich stimme zu, dass die Suche nach einem Poly-Time-Algorithmus ein guter Ausgangspunkt ist und Geheimnisse über das Problem enthüllt
Helium