Diskussion:NL (Komplexitätsklasse)

Beziehung zu anderen Komplexitätsklassen

Letzter Kommentar: vor 12 Jahren1 Kommentar1 Person ist an der Diskussion beteiligt

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)Beantworten