Komplexität von Sonderfallproblemen

Oft sehe ich einen solchen Satz, wenn ich Texte über Computational Complexity lese:

"Für diesen Sonderfall von " oder$\text{TSP}$

"Dies ist ein Sonderfall von " oder$\text{SAT}$

" - ist der folgende Sonderfall von " oder$k$$\text{PARTITION}$$\text{BIN PACKING}$

" ist ein Sonderfall von " ad nauseam.$\text{SUBSET SUM}$$\text{KNAPSACK}$

Was mir fehlt, ist das Kriterium, zu behaupten, ein Problem sei ein Sonderfall eines anderen.
Was ist die Notwendigkeit, ein Problem als Sonderfall eines anderen zu klassifizieren? Trägt ein Sonderfall immer die Komplexitätsklasse als "unspezifischen" Fall?

Oft wird dies einfach ohne Nachweis der Beziehung zwischen diesen Problemen angegeben.

Welche Voraussetzungen müssen erfüllt sein, damit ein Problem ein Sonderfall eines anderen ist?

Wie kann ich beweisen, dass eine neue Sprache für ein Problem ein Sonderfall eines bereits bestehenden Problems ist?

Wenn wir sagen, dass ein Problem ein Sonderfall eines Problems , meinen wir, dass dasselbe Problem wie , mit der Ausnahme, dass nicht alle Probleminstanzen von Probleminstanzen für . Wenn ein Sonderfall von , sagen wir, dass eine Verallgemeinerung von .$B$$A$$B$$A$$A$$B$$B$$A$$A$$B$

Zwei Beispiele: Die Addition positiver ganzer Zahlen (z. B. ) ist ein Sonderfall der Addition ganzer Zahlen (z. B. ) und der Sortierung von ganzen Zahlen im Bereich für festes ist ein Sonderfall zum Sortieren beliebiger Ganzzahlen.$5 + 3$$5 + (-3)$$\{ 1, 2, \dots, k \}$$k$

Jede Lösung für ist auch eine Lösung für , und jede Härte ergibt sich für (zum Beispiel ist sie hart oder benötigt Zeit, um gelöst zu werden) und wird sofort auf . Normalerweise betrachten wir jedoch Sonderfälle, da wir im Vergleich zum allgemeinen Fall manchmal bessere Algorithmen für sie finden können.$A$$B$$B$$NP$$\Omega(n^2)$$A$

Beispiele: Der Sortieralgorithmus funktioniert genauso gut für Ganzzahlen im Bereich , CountingSort jedoch für den Sonderfall (nicht für den allgemeinen Fall) in , was normalerweise schneller ist, wenn klein ist. ist -hard, ein Sonderfall ist , die immer noch ist -hard (was bedeutet deshalb , dass ist -hard), aber ist in .$\Theta(n \log n)$$\{ 1, 2, \dots, k \}$$O(n + k)$$k$$SAT$$NP$$3SAT$$SAT$$NP$$SAT$$NP$$2SAT$$P$

Beachten Sie, dass die obige Definition manchmal gestreckt (missbraucht) wird, um zu sagen, dass Sie jede Instanz von als Instanz von codieren können und dass diese Codierung äußerst einfach ist. In diesem Fall gilt das oben Gesagte normalerweise immer noch, ist jedoch weniger streng.$B$$A$

"Sonderfall" ist einfach das Gegenteil von "Allgemeinfall".

Zum Beispiel ist ein Baum ein Sonderfall eines Graphen usw. Dasselbe gilt für Probleme : "Finde das minimale Element einer Liste" oder "Finde den Median" sind nur Sonderfälle des Problems "Finde den ten kleinsten Element in der Liste ".$k$

Was die Komplexität betrifft, wissen wir, dass der Sonderfall höchstens so schwierig ist wie der allgemeine Fall (da jeder Algorithmus, der den allgemeinen Fall löst, auch den Sonderfall lösen kann).

Es ist jedoch möglich, dass der Sonderfall viel einfacher ist als der allgemeine Fall. Viele -vollständige Probleme haben Sonderfälle, die "einfach" zu lösen sind. Zum Beispiel 2- , der Sonderfall von bei dem die Formel in jeder Klausel nur 2 Variablen enthält. Während ist -komplette, 2- kann mit Polynomialzeit gelöst werden.$\text{NP}$$\text{SAT}$$\text{SAT}$$\text{SAT}$$\text{NP}$$\text{SAT}$

Ein weiteres Beispiel: Obwohl das Sortieren im Allgemeinen erfordert, gilt für den speziellen Fall, in dem die Domäne begrenzt ist (dh die Elemente stammen nur aus für ein festes ). gibt es eine lineare -Lösung unter Verwendung der Bucket-Sortierung usw.$\Omega(n\log n)$$\{1, \ldots, m\}$$m$$O(n+m)$