COMPSCI 61B Lecture Notes - Lecture 39: Kolmogorov Complexity, Complexity Class, Np-Completeness
28 Aug 2017
School
Department
Course
Professor
Document Summary
It just might be very hard to nd. De nition: the java-kolmogorov complexity k_j(b) is the length of the shortest java program (in bytes) that generates b. Fact #1: kolmogorov complexity is e ectively independent of language. For any bit stream, the java-kolmogorov complexity is no more than a constant factor larger than the python-kolmogorov complexity. Python interpreter in java and then run the python program. Fact #2: it is impossible to write a program that calculates the kolmogorov. Corollary: it is impossible to write the perfect compression algorithm. An independent set is a set of vertices in which no two vertices are adjacent. Does there exist an independent set of size k? (color k vertices red such that none touch) Check if number of colored vertices is equal to k: o(n) For every red vertex, check that neighbors are all white: o(k*n) If either check fails, go on to next coloring.
