Diskussion:NL (Komplexitätsklasse)
Letzter Kommentar: vor 12 Jahren von Nebenrechnung in Abschnitt Beziehung zu anderen Komplexitätsklassen
Beziehung zu anderen Komplexitätsklassen
[Quelltext bearbeiten]Im Artikel PSPACE steht, daß mindestens eine der Inklusionen
echt ist, daher ist aber natürlich auch die Inklusion NC ⊂ PSPACE echt. Dies steht aber im Widerspruch zu
In obiger Kette ist für keine Inklusion bekannt, ob sie echt ist. Die einzigen transitiven Inklusionen, für die die Echtheit bekannt ist, sind: [...]
aus dem Artikel.
- Ich verstehe deine Anmerkung nicht. Gemeint ist doch Folgendes: Die Inklusionen in der Kette sind: NC ⊆ P, P ⊆ NP, NP ⊆ PSPACE. Für keine von diesen Inklusionen ist bekannt, ob sie echt sind. Dass darüber hinaus transitive Inklusionen bekannt sind, widerspricht der obigen Aussage doch nicht. Ich sehe da also kein Problem. -- Nebenrechnung (Diskussion) 19:22, 22. Mär. 2012 (CET)