Warum ist die Klasse NP-Complete wichtig im Vergleich zu NP-Hard?

Ich lerne die Komplexität von Berechnungen und frage mich, warum die NP-Complete (NPC) -Probleme überhaupt eine wichtige Klasse sind. Ich finde es offensichtlich, warum wir daran interessiert sind, zu zeigen, dass ein bestimmtes NP-Problem NP-schwer ist.

Ich verstehe auch die Definition von NPC und dass es NP-schwer ist, ein bestimmtes Entscheidungsproblem zu zeigen, wenn man weiß, dass es sich um NP handelt, ist genau das, was NPC bedeutet.

Was ich jedoch nicht verstehe, ist: Warum ist dieses Konzept so wichtig? Wenn wir einen NP-harten Algorithmus finden, der in der Zeit P abläuft (unabhängig davon, ob dieser in NP ist oder nicht), haben wir sicherlich gezeigt, dass .$NP = P$

Warum ist dieses Konzept so wichtig?

Es gibt mindestens ein paar Gründe, warum NPC interessant ist:

• Die Klasse NP enthält viele interessante Probleme (sowohl praktisch als auch theoretisch). Darüber hinaus sind viele dieser Probleme NP-schwer (und daher NP-vollständig), aber viele Probleme außerhalb von NP sind mit ziemlicher Sicherheit zu schwer zu lösen mehr als theoretisches Interesse , daher bietet NPC eine (grobe) Gruppe von Problemen, die anscheinend schwierig sind, aber nicht so schwer, dass wir nicht versuchen können, etwas mit ihnen zu tun.
  Mit anderen Worten, NPC ist wahrscheinlich die Grenze dessen, was wir hoffen können, dass es polynomiell lösbar ist. Es scheint eine Strecke zu sein, es mit PSPACE = P zu versuchen (zum Beispiel).
• Die Klasse ist NP ist strukturell interessant. Es ist das grundlegende Beispiel für "Bekommen wir mehr Rechengeschwindigkeit durch Nichtdeterminismus?". Wir sind also daran interessiert, ob P = NP ist oder nicht, und NPC ist (wahrscheinlich) eine wichtige Komponente, um das herauszufinden.
• NP-hard (als Klasse) ist wirklich zu groß und variiert mit als eine einzige Sache zu tun, es ist alles, was von einem NP-vollständiges Problem reduziert werden kann , darunter eine riesige Schneise von Sachen außerhalb NP, so von dem Punkt der Angesichts des Versuchs, allgemeine Ergebnisse und Techniken zu entwickeln, gibt es nichts, woran man sich festhalten kann.

Aus der Sicht von jemandem, der Code für seinen Lebensunterhalt schreibt, ist eine gute Kenntnis der NP-Vollständigkeit wichtig für:

1. Erkennen, wann Sie den falschen Baum bellen

NP-vollständige Probleme sind die einfachsten der NP-harten Probleme. Soweit wir das beurteilen können, nimmt die Lösung eines solchen Entscheidungsproblems exponentiell viel Zeit in Anspruch. Wenn Sie also praktisch nachweisen können, dass das Problem, das Sie zu lösen versuchen, NP-schwer ist (in der Regel, indem Sie zeigen, dass eine effiziente Lösung auch eine effiziente Lösung für ein NP-vollständiges Problem darstellt), wissen Sie, dass dies der Fall ist Sie können aufhören, nach einem effizienten Algorithmus zu suchen , um ihn im Allgemeinen genau zu lösen. Stattdessen können Sie aus bekannten Algorithmen auswählen, die gute Näherungen für NP-harte Optimierungsprobleme versprechen, und mit dem Rest Ihres Projekts weitermachen.

2. Den richtigen Baum finden

Da Computer häufig für den Angriff auf NP-schwierige Probleme eingesetzt werden, wurden spezielle Löser entwickelt, mit denen einige NP-schwierige Problemfälle effizient gelöst werden können . Das Erkennen, dass Ihr Problem NP-vollständig ist, ist der erste Schritt, um ein vorhandenes Tool (SAT, ILP, SMT, CSP, um nur einige zu nennen) zu finden, mit dem Sie in einigen Fällen, in denen Sie sich andernfalls mit einem hätten zufrieden geben müssen, genaue Lösungen finden können Annäherung.

"Wenn wir einen NP-harten Algorithmus finden, der in der Zeit P abläuft (ob das nun in NP ist oder nicht), haben wir gezeigt, dass NP = P ist. Warum ist dieses Konzept so wichtig?"

Jedes NP-Problem reduziert sich auf ein NPC-Problem, aber es ist nicht wahr, dass jedes NP-Problem auf ein NP-hartes Problem reduziert wird, so dass der Beweis, dass ein Algorithmus NP-hart ist, in P nicht beweist, dass P = NP ist. Für ein NPC-Problem wäre es jedoch genau das, was "reduziert" bedeutet. Wenn wir also einen P-Algorithmus für ein NPC-Problem finden, haben wir bewiesen, dass P = NP ist.