Nonuniform complexity and the randomness of certain complete languages

DOI10.1016/0304-3975(92)90340-LzbMath0755.68078MaRDI QIDQ1184988

Dung T. Huynh

Publication date: 28 June 1992

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

Kolmogorov complexityrandom sequenceshard problems

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Grammars and rewriting systems (68Q42)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Concise description of finite languages
• Time-bounded grammars and their languages
• Some Observations about the Randomness of Hard Problems
• A complexity theory based on Boolean algebra
• Languages Simultaneously Complete for One-Way and Two-Way Log-Tape Automata
• On Isomorphisms and Density of $NP$ and Other Complete Sets
• On the Tape Complexity of Deterministic Context-Free Languages
• The Hardest Context-Free Language
• Finite-Turn Pushdown Automata
• On the Length of Programs for Computing Finite Binary Sequences

This page was built for publication: Nonuniform complexity and the randomness of certain complete languages