Warum haben NP-vollständige Probleme keine ähnlichen Approximationsverhältnisse?

11

Da 2 NP-vollständige Probleme per Definition auf einander reduzierbar sind, kann eine Lösung für eines von ihnen erhalten werden, indem eine Black-Box verwendet wird, die das andere löst. Warum haben sie keine ähnlichen Approximationsverhältnisse (bezogen auf ihre Optimierungsgegenstücke)? )? Ich denke, dass eine konstante oder sogar Polynomdrift verstanden werden könnte, aber wir haben den Fall von Näherungsalgorithmen mit konstantem Faktor für einige NP-vollständige Probleme und andererseits für andere Probleme, die durch einen Näherungsalgorithmus mit Polynomverhältnis nicht einmal angenähert werden können , wie allgemeiner TSP? Vielen Dank

cc.complexity-theory approximation-algorithms reductions N27
quelle
11
weil die Black-Box-Reduzierungen nur den JA / NEIN-Aspekt der (Entscheidungs-) Probleme bewahren, nicht die Nähe der Annäherungen.
Suresh Venkat
6
Wenn ich 3SAT auf die Scheitelpunktabdeckung reduziere, impliziert die Scheitelpunktabdeckung der Größe k die Erfüllbarkeit und umgekehrt. Wenn ich jedoch eine Scheitelpunktabdeckung der Größe 2k erhalte, bedeutet dies nicht, dass ich die Hälfte der Klauseln erfüllen kann.
Suresh Venkat
13
Wählen Sie eine bestimmte Reduzierung von einem NP-vollständigen Problem zu einem anderen und versuchen Sie, sie zu erweitern, um die Approximationsverhältnisse beizubehalten. Du wirst sehen, was schief geht.
Peter Shor
5
Peters Antwort ist wirklich die beste. Probieren Sie es einfach aus und sehen Sie, was passiert. Ich denke, mit philosophischer Skepsis meinst du "Ich verstehe die Intuition nicht wirklich". Manchmal ist es am besten, nur einige Beispiele auszuprobieren und die Intuition wachsen zu lassen.
Suresh Venkat
8
Ein weiterer Weg, um Ihre Intuition zu steigern: Nehmen Sie das Problem der Scheitelpunktabdeckung und ändern Sie die Zielfunktion. Minimierevs.vs. vs. über alle Scheitel Abdeckungen . Für jede Variante ist die Menge der optimalen Lösungen genau gleich. Einige der Versionen sind jedoch viel einfacher zu approximieren. Die Zielfunktion einer Optimierung ist etwas willkürlich und die Annäherbarkeit hängt stark von der Wahl der Zielfunktion ab. In der Tat ist das Problem der maximalen unabhängigen Menge nur das Problem der minimalen Scheitelpunktabdeckung mit einer seltsamen Zielfunktion. log⁡|C||C||C|22|C|C
Jukka Suomela

Antworten:

6

Reduzierungen werden in Bezug auf die Entscheidungsversion der Probleme definiert. Approximationsverhältnisse für ihre Optimierungsversionen sind eine separate Frage, die verwandt zu sein scheint, aber nicht unbedingt sein muss. Um Ihre Frage aus philosophischer Sicht mit einer Frage zu beantworten, warum sollten Sie erwarten, dass der Klassen-NPC Approximationsverhältnisse beibehält, wenn sie überhaupt nicht in Bezug auf sie definiert sind?

Lev Reyzin
quelle
"Reduzierungen werden in Bezug auf die Entscheidungsversion der Probleme definiert." Gilt das beispielsweise für Levin-Reduktionen ?
MS Dousti
Sie haben Recht, nicht alle Reduzierungen sind für Entscheidungsversionen definiert, aber wir können NPC nur in Bezug auf Black-Box-Reduzierungen definieren, und dann kann dies zu Debatten darüber führen, wie sich diese Klassen mit der verwendeten Reduktion ändern ... Ich hätte sagen sollen: "Der Klassen-NPC ist für Entscheidungsprobleme definiert." Es ist nicht wirklich ein genaues Argument, da wir sogar eine Klasse von Entscheidungsproblemen definieren könnten, deren Optimierungsversionen Approximationsverhältnisse beibehalten, aber das tun wir nicht für den Klassen-NPC. Ich denke, die Frage von @ N27 ist ein philosophischer Einwand. Ich darf eine philosophische Antwort geben. :)
Lev Reyzin