Diskussion:Deskriptive Komplexitätstheorie

aus Wikipedia, der freien Enzyklopädie
Letzter Kommentar: vor 10 Jahren von 134.61.169.202 in Abschnitt Nicht ganz korrekt
Zur Navigation springen Zur Suche springen

Nicht ganz korrekt

[Quelltext bearbeiten]

Unter dem Punkt "Weitere Charakterisierungen" steht: verschiedene Fixpunktlogiken beschreiben P beziehungsweise PSPACE.

Das ist aber nicht ganz richtig, es ist bislang noch ein offenes Problem, ob eine Logik existiert, die P charakterisiert. Man weiß, dass in der Domäne der endlichen geordneten Strukturen P durch LFP/IFP und PSPACE durch PFP charakterisiert werden, allerdings ist diese Frage bei Strukturen ohne vorhandene Ordnung noch nicht geklärt. Insbesondere ist noch nicht bewiesen oder widerlegt, ob die Inklusionen und für Strukturen ohne definierbare Ordnung gültig sind.

--37.24.144.36 00:31, 26. Jun. 2013 (CEST)Beantworten

Dachte mir gerade das gleiche und habe das ergänzt. Muss nur gesichtet werden. --134.61.169.202 13:19, 28. Jan. 2014 (CET)Beantworten