Diskussion:Erreichbarkeitsproblem in Graphen
Platzverbrauch O(1)? Ich bin mir nicht sicher, ob der Platzverbrauch wirklich O(1) ist, um einen Knoten zu speichern. Angenommen, man hat n Knoten, die binär codiert werden, dann ist der Platzverbrauch mit O(log(n)) beschränkt.
-- 83.216.231.212 12:12, 16. Jun. 2007 (CEST) Sebastian
Platzverbrauch O(1)? Das ist falsch. Ein Knoten kann nicht von nur einer Zelle gespeichert werden weil dann Eingabealphabet nicht mehr endlich. wäre. Richtig wäre O(log(n)).
Platzverbrauch O(1)? Bin auch der Meinung dass das falsch ist, sonst wäre ja GAP eine reguläre Sprache, denn REG = NSPACE(1)?! (nicht signierter Beitrag von 79.235.164.246 (Diskussion) 18:23, 17. Aug. 2010 (CEST))
AKTUALISIERUNGSBEDARF[Quelltext bearbeiten]
Omer Reingold hat 2005 das Problem mit einem Logarithmischen Aufwand lösen können. Dafür erhielt er den Grace Murray Hopper Award. siehe auch hier: http://de.wikipedia.org/wiki/Grace_Murray_Hopper_Award