Symmetry theorem

25 novembro 2014, 17:30 • Paulo Alexandre Carreira Mateus

Proof that C(<x,y>) <= C(x) + C(y) +O(log min C(x), C(y)) and why the log term cannot be avoided.

Language compression Theorem.

Kolmogorov complexity proof that BPP is contained in P/Poly.

Symmetry of information for Algorithm Information theory. Theorem and proof.

Lecture given by André Souto