Random languages for nonuniform complexity classes

DOI10.1016/0885-064X(91)90038-YzbMath0796.68097MaRDI QIDQ1179458

Rainer Schuler, Martin Mundhenk

Publication date: 26 June 1992

Published in: Journal of Complexity (Search for Journal in Brave)

zbMATH Keywords

Kolmogorov complexitynonuniform complexity classesnonuniform space classesrandom languages

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (2)

A note on balanced immunity ⋮ Strong self-reducibility precludes strong immunity

Cites Work

• On the notion of infinite pseudorandom sequences
• On solving hard problems by polynomial-size circuits
• On characterizations of the class PSPACE/poly
• Complexity of Presburger arithmetic with fixed quantifier dimension
• Pseudorandom sources for BPP
• How to Generate Cryptographically Strong Sequences of Pseudorandom Bits
• Some Observations about the Randomness of Hard Problems
• Algorithms and Randomness
• On the Length of Programs for Computing Finite Binary Sequences
• The definition of random sequences
• A formal theory of inductive inference. Part II
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Random languages for nonuniform complexity classes