搜索结果: 1-4 共查到“Kolmogorov Complexity”相关记录4条 . 查询时间(0.125 秒)
Kolmogorov Complexity, Circuits, and the Strength of Formal Theories of Arithmetic
Complexity Circuits Strength of Formal Theories
2012/12/4
Can complexity classes be characterized in terms of efficient reducibility to the (undecidable) set of Kolmogorov-random strings? Although this might seem improbable, a series of papers has recently p...
Conditional Kolmogorov Complexity and Universal Probability
Conditional Kolmogorov Complexity Universal Probability Information Theory
2012/6/21
The conditional in conditional Kolmogorov complexity commonly is taken to be a finite binary string. The Coding Theorem of L.A. Levin connects unconditional prefix Kolmogorov complexity with the discr...
Kolmogorov complexity, Lovasz local lemma and critical exponents
Kolmogorov complexity Lovasz local lemma critical exponents
2010/12/13
D. Krieger and J. Shallit have proved that every real number greater than 1 is a critical exponent of some sequence [1].We show how this result can be derived from some general statements about sequen...
Forbidden substrings, Kolmogorov complexity and almost periodic sequences
Forbidden substrings Kolmogorov complexity almost periodic sequences
2010/12/10
Assume that for some < 1 and for all nutural n a set Fn of at most 2 n “forbidden” binary strings of length n is fixed. Then there exists an infinite binary sequence ! that does not have (long) forb...