Diskussion:NC (Komplexitätsklasse)

hier muss noch aufgenommen werden:

• Beziehung von NC zu P
• NC und P-Vollständigkeit
• Links und siehe auch

--Mkleine 01:07, 13. Jan 2005 (CET)

• interessante Probleme, die in NC liegen. --zeno 22:17, 13. Jan 2005 (CET)

Definition

Ich kenne nur die Definition von NC mithilfe von Schaltkreisfamilien mit polynominaler Größe und polylograithmischer Tiefe. Vermutlich sind beide Definitionen äquivalent. Ich frage mich jetzt aber, was früher da war. -- MlaWU 15:04, 1. Mär 2005 (CET)

Das ist prinzipiell nicht sonderlich überraschend, da die meisten Komplexitätsklassen auf sehr verschiedenen Wegen aufgebaut werden können. Da sich für unterschiedliche Berechnungsmodelle meist nur lineare Unterschiede ergeben, sind die Ansätze in diesem Sinne äquivalent. Eine alternative Definition fände ich für den Artikel durchaus interessant. Vielleicht kannst du ja eine präzise Version davon noch auftreiben? Ich denke, das würde den Artikel bereichern. Vermutlich dürfte die Schaltkreis-Version sogar die frühere sein, da Pippenger in diesem Bereich geforscht hat. Grüße --Mkleine 22:22, 1. Mär 2005 (CET)

In meiner Mitschrift steht dazu: $NC=\bigcup _{i=0}^{\infty }NC_{i}$ und $NC_{i}$ wird dann definiert als die Klasse aller Entscheidungsprobleme, die eine uniforme Schaltkreisfamilie mit polynominaler Größe und $O(\log ^{i}(n))$ Tiefe und einen fan-in von höchstens 2 lösen kann. Dann kommt noch die Aussage, daß $NC_{1}\subseteq DSPACE(log)$ und $NC_{2}\subseteq NSPACE(log)$. Mehr kann ich dazu auf die Schnelle auch nicht rausfinden. -- MlaWU 02:00, 2. Mär 2005 (CET)

Ich werde mir das bei Gelegenheit mal anschauen und versuchen, in den Artikel einzuarbeiten. Grüße --Mkleine 03:17, 2. Mär 2005 (CET)

P Teilmenge von NC?

Muss der Satz im letzten Abschnitt nicht genau anders herum? Muss nicht i.A. davon ausgegangen werden, dass P echte Teilmenge von NC ist und nicht umgekehrt? Oder spielt mit der niedrige morgendliche Kaffeepegel einen Streich? --Triph 09:05, 19. Dez 2009 (CET)

Das stimmt schon so. Jedes Problem, das parallel mit polynomiellem Aufwand berechenbar ist, ist durch Simulation auch auf nur einem Prozessor mit polynomiellem Aufwand, also in polynomieller Zeit berechenbar. Das bedeutet $NC\subseteq P$. Ob aber jedes Problem mit polynomieller sequentieller Laufzeit auch in poly-logarithmischer Laufzeit lösbar ist, wenn man nur mit genügend Prozessoren danach schmeißt, ist fraglich. --GrGr 18:00, 28. Jun. 2007 (CEST)

Letzte Vermutung im Text

Im Artikel steht: Aufgrund der Vermutung NC ≠ P geht man also davon aus, dass es kein P-vollständiges Problem in NC gibt. Ist es nicht genau andersherum? Müßte dieser Satz nicht eher Da noch kein P-vollständiges Problem in NC gefunden wurde, geht man von NC ≠ P aus? lauten? FrankyS 20:20, 6. Feb. 2007 (CET)