imported>Thomas Dresler: Kommasetzung

2023-04-14T07:15:14Z

Kommasetzung

Neue Seite

In der [[Theoretische Informatik|theoretischen Informatik]] bezeichnet der '''Problemkern''' ([[Englische Sprache|engl]]. '''problemkernel''') den [[Algorithmus|algorithmisch]] „schwierig“ [[entscheidbar]]en Teil einer [[Probleminstanz|Instanz]] eines [[NP-Schwere]]n Problems. Viele Instanzen NP-schwerer Probleme enthalten Teilprobleme, die leicht entscheidbar sind. Zum Beispiel in vielen Instanzen von Problemen, bei denen eine Teilmenge ''S'' von einer Menge ''M'' gewählt werden soll, haben Elemente ''x'' von ''M'' gewisse Eigenschaften, durch die man [[Effizienz (Informatik)|effizient]] entscheiden kann, dass ''x'' in ''S'' sein muss oder nicht in ''S'' sein kann.

Die Methode, solche Elemente zu suchen und aus der Instanz zu entfernen, bezeichnet man als '''Problemkern-Reduktion''' ([[Englische Sprache|engl]]. '''kernelization'''). Die Elemente, die solche Eigenschaften nicht haben und nach Problemkern-Reduktionen übrig sind, bilden den Problemkern der Instanz.

== Beispiele ==
Bei Instanzen ''G'' des [[Färbung (Graphentheorie)|''q''-Färbungsproblems]] können sukzessive [[Knoten (Graphentheorie)|Knoten]] ''x'' entfernt werden, deren [[Grad (Graphentheorie)|Grad]] kleiner als ''q'' ist, weil in einer ''q''-Färbung des Restgraphen die [[Nachbarschaft (Graphentheorie)|Nachbarschaft]] von ''x'' höchstens ''q-1'' Farben enthält, womit mindestens eine Farbe für ''x'' übrig ist. Dadurch ist ''G'' genau dann ''q''-färbbar, wenn der Graph ''G’'', der sich aus ''G'' nach Entfernung des Knotens ''x'' ergibt, ''q''-färbbar ist.

Bei Instanzen ''(G,k)'' des parametrisierten [[Knotenüberdeckungsproblem]]s (d. h. bei der Suche nach einer Knotenüberdeckung der Größe ''k'') kann man sukzessive Knoten ''x'' auswählen, deren Grad größer als ''k'' ist. Diese müssen Teil der Knotenüberdeckung sein, weil die zu ''x'' [[Nachbarschaft (Graphentheorie)#Für ungerichtete Graphen|inzidenten]] [[Kante (Graphentheorie)|Kanten]] überdeckt werden müssen, wofür anderenfalls nur noch die gesamte Nachbarschaft von ''x'' in Frage käme. Dies wären aber mehr als ''k'' Knoten, womit sofort das Limit für die Größe der Knotenüberdeckung überschritten wäre. Dadurch besitzt ''G'' genau dann eine Knotenüberdeckung der Größe <math>\le k</math>, wenn ''G-x'' eine Knotenüberdeckung der Größe <math>\le k-1</math> besitzt.

Bei Instanzen ''G'' des [[Cliquenproblem|''q''-Cliquenproblems]] können sukzessive Knoten ''x'' entfernt werden, deren Grad kleiner als ''q-1'' ist, weil die Knoten einer ''q''-Clique mit den anderen ''q-1'' Knoten der Clique benachbart sind, woraus für diese Knoten ein Grad von mindestens ''q-1'' folgt. Dadurch besitzt ''G'' genau dann eine ''q''-Clique, wenn ''G-x'' eine ''q''-Clique besitzt.

Das vorausgesetzte Problem muss nicht notwendig [[entscheidbar]] oder [[Semi-entscheidbare Menge|semi-entscheidbar]] sein. Zum Beispiel entspricht auch die Entfernung von [[Erreichbarkeitsproblem in Graphen|unerreichbaren]] Zuständen einer [[Turingmaschine]] der Definition einer Problemkern-Reduktion für die (nicht semi-entscheidbare) Frage, ob die Turingmaschine eine [[partielle Funktion]] berechnet.

== Formale Definition ==
Sei <math>P\subseteq M\times\mathbb{N}</math> ein parametrisiertes Problem mit einer [[Norm (Mathematik)|Norm]] <math>|.|</math> auf <math>M</math>.

Eine Problemkern-Reduktion ist eine Funktion <math>f\colon M\times\mathbb{N}\rightarrow M\times\mathbb{N}</math> mit den Eigenschaften

# <math>(I,k)\in P \Leftrightarrow (I^\prime,k^\prime):=f(I,k)\in P</math> (Äquivalenz)
# <math>|I^\prime| \le |I|</math> und <math>k^\prime \le k</math> (Simplifikation)
# ''f'' ist in [[Polynomialzeit]] berechenbar

Problemkern-Reduktionen definieren je eine [[Transitive Relation|transitive]], [[Wohlfundierte Relation|wohlfundierte]] [[Ordnungsrelation]] ''R'' auf <math>M\times\mathbb{N}</math>. Ein Problemkern einer Instanz ''(I,k)'' ist eine [[Wohlfundierte Relation|''R''-Normalform]] von ''(I,k)'' bezüglich einer Problemkern-Reduktionsrelation ''R''. Problemkern-Reduktionen sind häufig [[Konfluenz (Informatik)|konfluent]], wodurch ihre Normalformen dann eindeutig sind. Daher spricht man oft auch von „dem“ Problemkern einer Instanz, wobei man aber außer Acht lässt, dass andere (möglicherweise noch unbekannte) Problemkern-Reduktionen zu noch kleineren Instanzen führen könnten.

== Obere Schranken für die Größe ==
Jedes entscheidbare, parametrisierte Problem, für das man garantieren kann, dass die Größe des Problemkerns jeder Instanz ''(I,k)'' beschränkt ist durch ''g(k)'', für eine beliebige Funktion ''g'', ist [[Parametrisierter Algorithmus|fixed parameter tractable]], da man nach einer Problemkern-Reduktion einen Algorithmus mit beliebiger (endlicher) Laufzeit ''h'' auf den Problemkern anwenden kann, womit sich eine Laufzeit von <math>poly(n)+h(g(k))</math> ergibt.

Umgekehrt hat jede Instanz ''(I,k)'' eines Problems, das fixed parameter tractable ist, einen Problemkern, der in Polynomialzeit berechenbar ist und dessen Größe durch ''g(k)'' beschränkt ist, für eine Funktion ''g''. Beweisskizze: Gegeben sei ein parametrisiertes Problem, das fixed parameter tractable ist, für das also ein Algorithmus existiert, der jede Instanz ''(I,k)'' mit einer Laufzeit von <math>f(k) |I|^c</math> löst. Eine Problemkern-Reduktion ist nun: wenn ''|I|<f(k)'' ist, dann ist ''(I,k)'' selbst ein geeigneter Problemkern (dessen Größe durch ''f(k)'' beschränkt ist). Anderenfalls kann man den FPT-Algorithmus benutzen, um zu ermitteln ob <math>(I,k)\in P</math> ist. Darauf basierend wählt man als Problemkern eine beliebige (aber fest gewählte) Instanz <math>I_\text{ja}\in P</math> oder <math>I_\text{nein}\not\in P</math>, womit die Größe jedes Problemkerns beschränkt ist durch <math>g(k) := \max\{f(k),|I_\text{ja}|,|I_\text{nein}|\}</math>. Entscheidend ist hierbei: Im Fall, dass ''f(k)<|I|'' ist, ist die Laufzeit des Algorithmus
<math>f(k) |I|^c \le |I|^{c+1}</math>, womit die polynomielle Laufzeit folgt.

Damit stellt sich heraus, dass die [[Komplexitätsklasse]] FPT genau der Klasse von parametrisierten Problemen entspricht, deren Problemkerne durch eine Funktion des Parameters beschränkt sind.

Trotzdem ist es auch bei Problemen, die nicht fixed parameter tractable sind, wo also nicht garantiert werden kann, dass der Problemkern relativ klein ist, sinnvoll, Problemkern-Reduktionen am Anfang jedes [[Rekursion]]saufrufs anzuwenden, da sie in der Praxis auch dort große Verbesserungen der [[Laufzeit (Informatik)|Laufzeiten]] bringen.

== Feinere Abstufung von FPT ==
Die unterschiedlichen Schranken für die Größe des Problemkerns liefern eine feinere Abstufung der Komplexitätsklasse FPT. Zum Beispiel ist das Knotenüberdeckungsproblem „leichter“ als das [[Min-Multicut]] Problem auf Bäumen, obwohl beide in FPT sind, weil der Problemkern einer Instanz des Knotenüberdeckungsproblems (nach Nemhauser und Trotter) höchstens Größe ''2k'' hat, wogegen die beste bekannte Problemkern-Reduktion für Min-Multicut auf Bäumen Problemkerne liefert, deren Größe durch <math>k^6</math> beschränkt ist. Beide befinden sich aber in der wichtigen Klasse ''POLYKERNEL'', welche die Probleme enthält, deren Instanzen Problemkerne haben, deren Größe durch ein [[Polynom]] in ''k'' beschränkt ist.

== Literatur ==
* Rolf Niedermeier: ''Invitation to Fixed-Parameter Algorithms''. Oxford University Press, Oxford 2006, ISBN 0-19-856607-7, (''Oxford Lecture Series in Mathematics and its Applications'' 31).

[[Kategorie:Komplexitätstheorie]]

Problemkern - Versionsgeschichte

imported>Thomas Dresler: Kommasetzung