Diskussion:Deskriptive Komplexitätstheorie

Nicht ganz korrekt

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 $P\subseteq LFP/IFP$ und $PSPACE\subseteq PFP$ für Strukturen ohne definierbare Ordnung gültig sind.

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

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