A relation between correctness and randomness in the computation of probabilistic algorithms

DOI10.1080/00207168408803423zbMATH Open0552.68051OpenAlexW2084686533WikidataQ57001812 ScholiaQ57001812MaRDI QIDQ3345786FDOQ3345786

Cristian S. Calude, Marius Zimand

Publication date: 1984

Published in: International Journal of Computer Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1080/00207168408803423

Recommendations

• scientific article; zbMATH DE number 4119313
• An observation on probability versus randomness with applications to complexity classes
• On elementary computability-theoretic properties of algorithmic randomness
• A generalized characterization of algorithmic probability
• Effective randomness for computable probability measures
• Computable Measure Theory and Algorithmic Randomness
• The equivalence of definitions of algorithmic randomness
• Randomness -- a computational complexity perspective
• Randomness – A Computational Complexity Perspective
• On stability of probability laws with respect to small violations of algorithmic randomness

zbMATH Keywords

probabilistic algorithmrandom stringsprobabilistic primality testsKolmogorov's complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Algorithms in computer science (68W99)

Cites Work

• Title not available (Why is that?)
• The definition of random sequences
• Riemann's hypothesis and tests for primality
• A Fast Monte-Carlo Test for Primality
• Computational Complexity of Probabilistic Turing Machines
• Title not available (Why is that?)
• A note on monte carlo primality tests and algorithmic information theory
• Strong noncomputability of random strings

Cited In (7)

• On using deterministic functions to reduce randomness in probabilistic algorithms
• Randomization, persuasiveness and rigor in proofs
• Honest iteration schemes of randomizing algorithms
• Title not available (Why is that?)
• Probability and program-size for functions
• On Assessing the Performance of Randomized Algorithms
• Title not available (Why is that?)

This page was built for publication: A relation between correctness and randomness in the computation of probabilistic algorithms

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