# The frequent paucity of trivial strings

@article{Lutz2014TheFP, title={The frequent paucity of trivial strings}, author={Jack H. Lutz}, journal={ArXiv}, year={2014}, volume={abs/1310.6383} }

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.

#### Topics from this paper

#### 2 Citations

Technical report column

- Computer ScienceSIGA
- 2014

“The two queries assumption and Arthur-Merlin classes,” VyasRam Selvam, TR13-144. “Two Structural Results for Low Degree Polynomials and Applications,” Gil Cohen, Avishay Tal, TR13-145. “A…

Research on a cluster system for binary data frames of wireless sensor network

- Computer ScienceCluster Computing
- 2016

As the development of network became more complex, protocol reverse engineering has attracted increasing attention and widely applied in intrusion detection, vulnerability discovery, and electronic…

#### References

SHOWING 1-10 OF 13 REFERENCES

The Probabilistic Method

- Computer ScienceSODA
- 1992

A particular set of problems - all dealing with “good” colorings of an underlying set of points relative to a given family of sets - is explored.

A New Approach to Formal Language Theory by Kolmogorov Complexity

- Mathematics, Computer ScienceSIAM J. Comput.
- 1995

This work presents a new approach to formal language theory using Kolmogorov complexity, an alternative for pumping lemma(s), a new characterization for regular languages, and a new method to separate deterministic context-free languages and nondeterministic context -free languages.

Algorithmic Randomness and Complexity

- Mathematics, Computer ScienceTheory and Applications of Computability
- 2010

This chapter discusses Randomness-Theoretic Weakness, Omega as an Operator, Complexity of C.E. Sets, and other Notions of Effective Randomness.

Information-Theoretic Characterizations of Recursive Infinite Strings

- Computer Science, MathematicsTheor. Comput. Sci.
- 1976

Loveland's method shows that this is no longer a sufficient condition for x to be recursive if one merely stipulates that K ( x n ) ⩽ K ( n ) + c for infinitely many n.

Computability and randomness

- Mathematics
- 2009

The interplay between computability and randomness has been an active area of research in recent years, reflected by ample funding in the USA, numerous workshops, and publications on the subject. The…

Instance complexity

- Mathematics, Computer ScienceJACM
- 1994

It is proved that if t(n)z n is a time-constructible function and A 1s a recurswe set not in DTIME(t), there then exist a constant c and mfimtely many I such that ic’(x :,4) z K’ (x) – c.

A Variant of the Kolmogorov Concept of Complexity

- Mathematics, Computer ScienceInf. Control.
- 1969

A simple variation of the (restricted) conditional complexity measure investigated by Martin-Lof is noted because of interesting characteristics not shared by the measures proposed by Kolmogorov.

An Introduction to Kolmogorov Complexity and Its Applications

- Computer Science, PsychologyTexts and Monographs in Computer Science
- 1993

The book presents a thorough treatment of the central ideas and their applications of Kolmogorov complexity with a wide range of illustrative applications, and will be ideal for advanced undergraduate students, graduate students, and researchers in computer science, mathematics, cognitive sciences, philosophy, artificial intelligence, statistics, and physics.

Additive combinatorics

- Computer ScienceCambridge studies in advanced mathematics
- 2007

The circle method is introduced, which is a nice application of Fourier analytic techniques to additive problems and its other applications: Vinogradov without GRH, partitions, Waring’s problem.

In - stance complexity

- Computability and Randomness
- 2009