Diskussion:NL (Komplexitätsklasse)

aus Wikipedia, der freien Enzyklopädie
Letzter Kommentar: vor 12 Jahren von Nebenrechnung in Abschnitt Beziehung zu anderen Komplexitätsklassen
Zur Navigation springen Zur Suche springen

Beziehung zu anderen Komplexitätsklassen

[Quelltext bearbeiten]

Im Artikel PSPACE steht, daß mindestens eine der Inklusionen

NCPNPPSPACE

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