Resource bounded randomness and computational complexity
From MaRDI portal
Publication:1566703
DOI10.1016/S0304-3975(98)00119-4zbMath0943.68081WikidataQ127866088 ScholiaQ127866088MaRDI QIDQ1566703
Publication date: 4 June 2000
Published in: Theoretical Computer Science (Search for Journal in Brave)
Related Items (8)
On encoding symbol degrees of array BP-XOR codes ⋮ Sub-computable Bounded Pseudorandomness ⋮ Functions that preserve p-randomness ⋮ A Theory of Bounded Inductive Rationality ⋮ How much randomness is needed for statistics? ⋮ Subcomputable Hausdorff function dimension ⋮ Improvements in the computing efficiency of the probabilities of the LIL test for the PRNG evaluation ⋮ A comparison of two approaches to pseudorandomness
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Weak completeness in \(\text{E}\) and \(\text{E}_{2}\)
- On the notion of infinite pseudorandom sequences
- Almost everywhere high nonuniform complexity
- Almost every set in exponential time is P-bi-immune
- Zufälligkeit und Wahrscheinlichkeit. Eine algorithmische Begründung der Wahrscheinlichkeitstheorie. (Randomness and probability. An algorithmic foundation of probability theory)
- How to Generate Cryptographically Strong Sequences of Pseudorandom Bits
- Can an individual sequence of zeros and ones be random?
- Category and Measure in Complexity Classes
- Measure on P: Robustness of the notion
- Genericity, Randomness, and Polynomial-Time Approximations
- Resource-bounded balanced genericity, stochasticity and weak randomness
- The Complexity and Distribution of Hard Problems
- The definition of random sequences
This page was built for publication: Resource bounded randomness and computational complexity
