Random languages for nonuniform complexity classes

DOI10.1016/0885-064X(91)90038-YMaRDI QIDQ1179458zbMATH OpenFDO

Authors Martin Mundhenk, Rainer Schuler

Publication date 26 June 1992

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

Full work available at URL https://doi.org/10.1016/0885-064X(91)90038-Y

zbMATH Keywords

Kolmogorov complexitynonuniform complexity classesnonuniform space classesrandom languages

Mathematics Subject Classification ID

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

Recommendations

• Nonuniform complexity and the randomness of certain complete languages
• On complexity classes and algorithmically random languages (extended abstract)
• Almost everywhere high nonuniform complexity

Cites work

• A formal theory of inductive inference. Part II
• Algorithms and Randomness
• Complexity of Presburger arithmetic with fixed quantifier dimension
• How to Generate Cryptographically Strong Sequences of Pseudorandom Bits
• scientific article; zbMATH DE number 3427210 (Why is no real title available?)
• scientific article; zbMATH DE number 3988704 (Why is no real title available?)
• scientific article; zbMATH DE number 4086981 (Why is no real title available?)
• scientific article; zbMATH DE number 3363526 (Why is no real title available?)
• scientific article; zbMATH DE number 3420624 (Why is no real title available?)
• On characterizations of the class PSPACE/poly
• On solving hard problems by polynomial-size circuits
• On the Length of Programs for Computing Finite Binary Sequences
• On the notion of infinite pseudorandom sequences
• Pseudorandom sources for BPP
• Some Observations about the Randomness of Hard Problems
• The definition of random sequences

Cited in

(6)

• Nonuniform complexity and the randomness of certain complete languages
• Necessary conditions for subclasses of random context languages
• Nondeterministic complexity in subclasses of convex languages
• A note on balanced immunity
• Strong self-reducibility precludes strong immunity
• scientific article; zbMATH DE number 4187790 (Why is no real title available?)

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1179458)