AbstractThis paper presents one method of using time-bounded Kolmogorov complexity as a measure of the complexity of sets, and outlines a number of applications of this approach to di erent questions in complexity theory. Connections will be drawn among the following topics: NE predicates, ranking functions, pseudorandom generators, and hierarchy theorems in circuit complexity.
RightsThis Item is protected by copyright and/or related rights.You are free to use this Item in any way that is permitted by the copyright and related rights legislation that applies to your use.For other uses you need to obtain permission from the rights-holder(s).
