Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
Laufzeit beim Verifizieren
Bei Präsenzaufgabe 35 haben wir aufgeschrieben, dass die Laufzeit eines Verifizierers für COL in O( |V| * log k + |E| ) sei. Soweit wir uns erinnern können, stammt das log k bzw. log_2 k vom Raten der Färbung, also vom Raten einer k-stelligen Binärzahl.
Im weiteren Verlauf des Algorithmus vergleicht man die Färbung zweier benachbarter Knoten. Warum geht das nun in O(1) und nicht auch in O(log_2 k)?
Weil das im Grunde nur
if (c(u) == c(v))then halte verwerfend ist
Zwei gigantomanische Primzahlen kann man also in O(1) vergleichen? Im Prinzip muss man doch Bit für Bit vergleichen…?
Warum ist die Begründung bei 35 b) dann, dass man x_1 bis x_k nicht in polynomieller Zeit erraten kann?
Man vergleicht aber Binärzahlen mit Länge log₂k, sonst wäre es beim Raten auch in O(1).
Aber leider blicke ich bei meiner eigenen Mitschrift gerade auch nicht ganz durch.
Ging es in der Aufgabe nicht um Färbbarkeit? c(x) gibt die Farbe zurück.
Ja, das sollte allerdings auch auf Indices funktionieren. Das ist kein komplexer Datentyp mehr und kann durch die HW effizient gelöst werden.
Hm, ich glaube Raten ist doch etwas komplexer als ein simpler „== Vergleich“.
Man könnte höchstens mal in seinen KompAlg-Mitschriften rumwühlen und nachsehen wie das da gemacht wurde. Eine Garantie auf Übertragbarkeit auf BFS gäbe es dabei aber nicht.