Resource bounded randomness and computational complexity

DOI10.1016/S0304-3975(98)00119-4MaRDI QIDQ1566703zbMATH OpenWikidataFDO

Authors Y. Wang

Publication date 4 June 2000

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

zbMATH Keywords

computational complexitylaw of the iterated logarithmrandomness

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Recommendations

• scientific article; zbMATH DE number 969633
• scientific article; zbMATH DE number 1492083
• scientific article; zbMATH DE number 1048036
• Resource bounded randomness and weakly complete problems
• Resource-bounded measure on probabilistic classes

Cites work

• scientific article; zbMATH DE number 3988704 (Why is no real title available?)
• scientific article; zbMATH DE number 192916 (Why is no real title available?)
• scientific article; zbMATH DE number 1555954 (Why is no real title available?)
• scientific article; zbMATH DE number 969633 (Why is no real title available?)
• scientific article; zbMATH DE number 3249395 (Why is no real title available?)
• Almost every set in exponential time is P-bi-immune
• Almost everywhere high nonuniform complexity
• Can an individual sequence of zeros and ones be random?
• Category and Measure in Complexity Classes
• Genericity, Randomness, and Polynomial-Time Approximations
• How to Generate Cryptographically Strong Sequences of Pseudorandom Bits
• Measure on P: Robustness of the notion
• On the notion of infinite pseudorandom sequences
• Resource-bounded balanced genericity, stochasticity and weak randomness
• The Complexity and Distribution of Hard Problems
• The definition of random sequences
• Weak completeness in \(\text{E}\) and \(\text{E}_{2}\)
• Zufälligkeit und Wahrscheinlichkeit. Eine algorithmische Begründung der Wahrscheinlichkeitstheorie. (Randomness and probability. An algorithmic foundation of probability theory)

Cited in

(11)

• On Resource-Bounded Versions of the van Lambalgen Theorem
• A comparison of two approaches to pseudorandomness
• Sub-computable bounded pseudorandomness
• On encoding symbol degrees of array BP-XOR codes
• Subcomputable Hausdorff function dimension
• On pseudorandomness and resource-bounded measure
• scientific article; zbMATH DE number 1104167 (Why is no real title available?)
• Resource-bounded balanced genericity, stochasticity and weak randomness
• Improvements in the computing efficiency of the probabilities of the LIL test for the PRNG evaluation
• Closure of resource-bounded randomness notions under polynomial-time permutations
• A Theory of Bounded Inductive Rationality

This page was built for publication: Resource bounded randomness and computational complexity

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