Diskussion:Parametrisierter Algorithmus

FPT-Reduktion: Größe der Lösung

Nach der Definition der FTP-Reduktion heisst es: Dies ist eine Einschränkung gegenüber Polynomialzeitreduktionen, weil sich bei diesen die Größe der Lösung beliebig verändern kann. Warum darf sich bei der FTP-Reduktion die Größe der Lösung denn nicht beliebig ändern? Das geht aus der Definition nicht hervor. Der Parameter muss ja nicht zwangsläufig mit der Größe der Lösung korrespondieren oder wie ist das gemeint? --Decay 16:58, 15. Feb. 2010 (CET)

Courcelles Theorem/erweiterte MS2-Logik

Die "Erweiterung" der Logik um die min/max Quantoren ist keine echte Erweiterung. Man kann diese auch mithilfe von Allquantoren und Existenzquantoren ausdrücken. Hier muss ein Missverständnis vorliegen, denn Downey und Fellows schreiben dazu:

„Actually, this language is sometimes referred to in the literature as the extended monadic second-order language, and the logic the extended monadic second-order logic or MS2 logic. This is because we are looking at a two-sorted structure with predicates for edges and vertices plus an incidence relation.“

Der Zusatz "erweitert" bezieht sich also darauf, dass es zwei Sorten von Elementen gibt: Knoten und Kanten. Außerdem steht der Zusatz nicht vor MS2, sondern vor monadische Logik zweiter Stufe. Das Theorem bezieht sich auf Sätze der erweiterten monadischen Logik zweiter Stufe – oder kurz – der MS2-Logik

Auch wenn der Abschnitt in seiner aktuellen Form nicht unbedingt falsch ist, würde ich vorschlagen ihn zu überarbeiten, sodass keine unnötigen Missverständnisse entstehen. A. Ludwig (Diskussion) 16:28, 7. Jan. 2015 (CET)

Einleitung

Was ist mit dem Abschnitt

"In der Praxis ist f oft eine unangenehme Funktion wie $k^{n}$, man geht im Allgemeinen aber davon aus, dass k sehr klein ist (weil dies bei Instanzen, die in der Praxis vorkommen, häufig der Fall ist) und n groß werden kann."

gemeint? f sollte doch nur von k abhängen und nicht von n, und die gesamte Funktion sollte schon gar nicht exponentiell in n sein. (Natürlich könnten n und k hier eine andere Bedeutung haben als vorher, aber das müsste man dann auch schreiben). --Maformatiker (Diskussion) 17:47, 29. Aug. 2016 (CEST)

Im folgenden Abschnitt sind einige Fehler enthalten: Für Klassen von Graphen, die dadurch charakterisiert sind, dass ein planarer Graph als Minor verboten ist, sind alle diese Probleme in Polynomialzeit berechenbar, weil diese Graphklassen je eine konstante obere Schranke für die Baumweite haben. Dies betrifft zum Beispiel die Klasse der triangulierten Graphen und die Klasse der Wälder.

1. Jeder (nichtleere) Graph hat mind. einen planaren Minor. 2. Wälder und triangulierte Graphen sind planare graphen. 3. Triangulierte Graphen haben keine beschränkte Baumweite.

Sieht nach einer Mischung aus Übertragungs- und Logikfehlern aus...