Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR13-161 | 7th May 2014 04:59

The Frequent Paucity of Trivial Strings

RSS-Feed




Revision #1
Authors: Jack H. Lutz
Accepted on: 7th May 2014 04:59
Downloads: 520
Keywords: 


Abstract:

A 1976 theorem of Chaitin can be used to show that arbitrarily dense sets of lengths n have a paucity of trivial strings (only a bounded number of strings of length n having trivially low plain Kolmogorov complexities). We use the probabilistic method to give a new proof of this fact. This proof is much simpler than previously published proofs, and it gives a tighter paucity bound.


Paper:

TR13-161 | 23rd October 2013 23:05

The Frequent Paucity of Trivial Strings





TR13-161
Authors: Jack H. Lutz
Publication: 22nd November 2013 11:58
Downloads: 1403
Keywords: 


Abstract:

A 1976 theorem of Chaitin, strengthening a 1969 theorem of Meyer,says that infinitely many lengths n have a paucity of trivial strings (only a bounded number of strings of length n having trivially low plain Kolmogorov complexities). We use the probabilistic method to give a new proof of this fact. This proof is much simpler than previously published proofs. It also gives a tighter paucity bound, and it shows that the set of lengths n at which there is a paucity of trivial strings is not only infinite, but has positive Schnirelmann density.



ISSN 1433-8092 | Imprint