Nonuniform complexity and the randomness of certain complete languages (Q1184988): Difference between revisions
From MaRDI portal
Latest revision as of 16:16, 15 May 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Nonuniform complexity and the randomness of certain complete languages |
scientific article |
Statements
Nonuniform complexity and the randomness of certain complete languages (English)
0 references
28 June 1992
0 references
The author continues his investigations of the randomness properties of various languages. Using basic approaches of A. Church on infinite random sequences and A. N. Kolmogorov on finite random strings, the author exploits his earlier results on several concepts of random languages and properties of complete languages in terms of these randomness concepts from the complexity viewpoint rather than, say, the cryptography viewpoint. The author proves several interesting results that clarify the difficult relationships between resource-bounded Kolmogorov complexity and other non-uniform complexity measures defined by grammars or automata size. In the process, the author vindicates the naturalness of the use of the notion of weakly random languages.
0 references
hard problems
0 references
random sequences
0 references
Kolmogorov complexity
0 references