Fact-checked by Grok 2 weeks ago

Monte Carlo algorithm

In computing, a Monte Carlo algorithm is a randomized algorithm that produces the correct output with high probability but may return an incorrect result with a small, bounded probability of error.^[1] These algorithms leverage randomness to solve complex problems efficiently, particularly decision problems where deterministic methods are intractable, by accepting a controlled risk of error rather than requiring certainty. The term "Monte Carlo" originates from the probabilistic simulation techniques developed in the 1940s for nuclear physics calculations during the Manhattan Project, reflecting the role of chance in the process.^[2] The modern concept of Monte Carlo algorithms was introduced by Michael Rabin in the mid-1970s, building on earlier probabilistic ideas to enable practical solutions for problems like primality testing.^[3] Unlike Las Vegas algorithms, which always produce correct outputs but have variable runtime, Monte Carlo algorithms have fixed runtime with possible errors that can be amplified or reduced through repetition. They are fundamental in complexity theory, defining classes like BPP (bounded-error probabilistic polynomial time), and find applications in computational number theory for tasks such as polynomial identity testing and approximate counting, as well as in optimization and machine learning.^[4]

Fundamentals

Definition and Characteristics

A Monte Carlo algorithm is a randomized algorithm that employs random sampling to approximate solutions to complex computational problems, executing in polynomial time while providing the correct output with a bounded probability of error.^[5] These algorithms model decision problems or approximations using probabilistic Turing machines that access random bits, ensuring termination in a fixed amount of time independent of the random choices made.^[6] Key characteristics of Monte Carlo algorithms include their guaranteed polynomial-time runtime and the ability to achieve high correctness probability, typically at least $1 - 1/n^k for some constant k > 0, by repeating independent runs and taking a majority vote or union bound to amplify success rates.^[7] This contrasts with deterministic algorithms, which require exact computation without randomness but often face exponential time complexity for the same problems; Monte Carlo methods leverage randomness to enable efficient approximations or decisions with probabilistic guarantees rather than absolute certainty.^[8] A representative example is the estimation of \pi using random sampling: consider a unit square enclosing a quarter-circle of radius 1 centered at the origin; generate N points uniformly at random within the square, count the proportion p that lie inside the quarter-circle (i.e., satisfying x^2 + y^2 \leq 1), and approximate \pi \approx 4p, where the law of large numbers ensures convergence as N grows.^[9] The mathematical foundation for error bounding in Monte Carlo algorithms often draws from concentration inequalities, such as the Chernoff bound, which guarantees that the probability of significant deviation from the true value is at most \varepsilon \leq 1/2 for a single execution, with further reductions possible through repetition to achieve arbitrarily small error probabilities in polynomial time.^[6]

Historical Development

The Monte Carlo algorithm traces its origins to the 1940s at Los Alamos National Laboratory, where it was developed amid the Manhattan Project to model complex nuclear processes, particularly neutron diffusion and chain reactions in atomic bombs. Mathematicians Stanislaw Ulam and John von Neumann pioneered the approach, leveraging random sampling to approximate solutions to problems that were intractable through deterministic computation due to their high dimensionality and uncertainty.^[10] The name "Monte Carlo" was coined by Nicholas Metropolis, inspired by Stanislaw Ulam's uncle, who was known for gambling at the casino in Monaco.^[11] In 1949, Nicholas Metropolis and Stanislaw Ulam formalized the concept in their influential paper, introducing the term "Monte Carlo method" and outlining its statistical framework for solving mathematical problems through repeated random experiments.^[12] This publication highlighted the method's first practical applications, such as estimating definite integrals by generating random points within a domain and using the proportion falling under a curve to approximate areas—a technique rooted in the law of large numbers.^[12] Over the subsequent decades, these simulation techniques were refined for broader physical and engineering simulations, establishing Monte Carlo as a cornerstone of computational physics.^[13] By the 1970s, Monte Carlo principles began integrating into computational complexity theory, as researchers like Manuel Blum and Michael Rabin explored randomized computation models to address efficiency in decision problems.^[14] Rabin's work on probabilistic algorithms, including early analyses of nondeterministic processes, laid groundwork for classifying computations under uncertainty, while Blum's contributions to abstract complexity measures helped frame randomized strategies within formal hierarchies.^[15] A landmark milestone came in 1977 with the Solovay-Strassen primality test, the first explicit Monte Carlo algorithm for a decision problem, which used randomness to verify primality with one-sided error, running in polynomial time and marking a shift toward algorithmic applications beyond pure simulation. In the 1980s, Monte Carlo algorithms evolved further in computer science, transitioning from specialized simulation tools to versatile randomized paradigms applicable to optimization, graph problems, and numerical analysis, with increased focus on error bounds and amplification to ensure reliability.^[16] This period saw extensions of early sampling ideas to discrete decision tasks, solidifying Monte Carlo's role in bridging probabilistic methods with deterministic complexity classes.^[17]

Error Analysis

One-Sided versus Two-Sided Error

In Monte Carlo algorithms, the nature of probabilistic errors distinguishes between one-sided and two-sided variants, impacting their reliability for decision problems. One-sided error occurs when the algorithm guarantees correctness on one type of input while bounding the error probability on the other. Specifically, for a decision problem with "yes" and "no" instances, a one-sided error algorithm ensures that Pr[error | no] = 0, meaning it always correctly rejects "no" instances, but Pr[error | yes] ≤ ε for some small ε > 0, allowing it to potentially err by rejecting a "yes" instance (a false negative). This asymmetry provides stronger guarantees on one side, making such algorithms suitable for scenarios where false positives are intolerable, such as certain verification tasks. The dual form has Pr[error | yes] = 0 (always accept "yes" instances correctly) but Pr[error | no] ≤ ε (possible false positive by accepting "no" instances). In contrast, two-sided error algorithms permit bounded errors on both input types, with Pr[error] ≤ ε regardless of whether the input is a "yes" or "no" instance, typically setting ε to 1/3 for practical purposes. This bilateral risk can enable more efficient computations in cases where exactness on either side is not required, often leading to faster runtimes or simpler implementations compared to their one-sided counterparts. The trade-off is that two-sided errors may necessitate additional verification steps in applications demanding high precision on both outcomes. Seminal formalizations of these error models appear in the definitions of complexity classes, where one-sided error aligns with randomized polynomial-time computations (RP) that err only on "yes" instances by possibly rejecting them or the dual co-RP that errs only on "no" instances by possibly accepting them, while two-sided error supports bounded-error probabilistic computations (BPP).^[18] A prominent example of one-sided error in Monte Carlo algorithms is found in primality testing, where algorithms like the Solovay-Strassen test always correctly confirm primes ("yes" instances) but may occasionally declare a composite ("no" instance) as prime with probability at most 1/2, reducible by repetition. This one-sided property (co-RP) ensures no false declarations of compositeness for primes, which is crucial for cryptographic applications. In complexity terms, the RP class encompasses problems solvable in polynomial time with zero error on "no" instances and bounded error on "yes," whereas co-RP has zero error on "yes" instances and bounded error on "no," and two-sided error defines the BPP class, allowing efficient solutions to problems like parity or majority with errors bounded symmetrically. These distinctions highlight how error sidedness influences algorithmic design and theoretical classification.^[19]

Error Amplification and Reduction

In Monte Carlo algorithms, error amplification reduces the probability of incorrect output by executing the procedure multiple times with independent random choices and aggregating the results via voting mechanisms tailored to the error type. For two-sided error algorithms, where the initial error probability ε satisfies 0 < ε < 1/2, the algorithm is run t times independently, and the output is determined by the majority vote among the t results. This exponentially decreases the error probability, as the number of correct outcomes concentrates around its expectation using tail bounds. For one-sided error algorithms, repetition employs logical AND for cases with bounded error on acceptance (requiring all runs to accept for overall acceptance, as in co-RP) or OR for bounded error on rejection (requiring at least one acceptance for overall acceptance, as in RP), similarly yielding exponential error decay.^[20]^[21] The error reduction is rigorously bounded using Chernoff inequalities on the binomial distribution of correct outcomes. Consider a two-sided error Monte Carlo algorithm with success probability p = 1 - ε > 1/2 per run; after t independent runs, let X be the number of successes, so E[X] = p t. The amplified error probability under majority vote is Pr[X ≤ t/2] ≤ exp(- (p t - t/2)^2 / (2 p t) ) ≤ exp(-t (p - 1/2)^2 / (2 p) ) by the Chernoff bound for the lower tail. For standard BPP algorithms with ε ≤ 1/3 (so p ≥ 2/3), this simplifies to Pr[error] ≤ exp(-t / 72) after t repetitions. In the balanced case near ε = 1/4 (p = 3/4), amplification yields Pr[error] ≤ 2^{-t} with appropriate t. For one-sided errors with detection probability at least 1/2, repetition with OR/AND gives Pr[error] ≤ (1/2)^t directly from independence, without needing concentration bounds.^[20]^[22] Beyond repetition, error reduction techniques include adjusting the source of randomness to minimize variance in the output distribution, such as employing limited-independence random variables that approximate full randomness while using fewer bits, thereby preserving concentration guarantees like Chernoff bounds with reduced computational overhead. Hybrid approaches combine Monte Carlo amplification with derandomization methods, using pseudorandom generators to replace true randomness with short seeds, achieving near-deterministic behavior under cryptographic assumptions while maintaining exponentially small error. These hybrids, as in Impagliazzo-Wigderson derandomization, transform BPP algorithms into deterministic ones with mild slowdown for specific promise problems.^[23]^[24] A prominent example is the Solovay-Strassen primality test, a one-sided Monte Carlo algorithm that declares a composite number prime with probability at most 1/2 per run. By repeating the test k times with independent random bases and accepting only if all runs declare prime (AND combination), the composite-error probability drops to at most (1/2)^k; for k = 100, this yields error below 10^{-30}, making the test practically deterministic for cryptographic key generation.^[25]^[19]

Theoretical Foundations

Complexity Classes

Monte Carlo algorithms are central to several randomized complexity classes, which capture decision problems solvable by probabilistic Turing machines with bounded running time and controlled error probabilities. The class RP (Randomized Polynomial time) consists of decision problems for which there exists a polynomial-time probabilistic algorithm that accepts "yes" instances with probability at least 1/2 and rejects all "no" instances with probability 1, allowing one-sided error only on accepting inputs.^[26] These algorithms exemplify the Monte Carlo approach, as they run in worst-case polynomial time but may err on positive instances.^[26] The class BPP (Bounded-error Probabilistic Polynomial time) extends this to two-sided error, encompassing problems solvable in polynomial time by a probabilistic algorithm that outputs the correct answer with probability at least 2/3 for every input.^[27] Most practical Monte Carlo algorithms fall within BPP, where errors can occur on both "yes" and "no" instances but are bounded away from 1/2.^[28] Monte Carlo methods define the error-prone variants of these classes, distinguishing them from zero-error alternatives by permitting small, controllable inaccuracies in exchange for efficiency.^[26] In contrast, ZPP (Zero-error Probabilistic Polynomial time) includes problems solvable with no error probability, but in expected polynomial time, often via algorithms that may rerun on inconclusive outcomes.^[28] This class bridges deterministic and randomized computation, incorporating Monte Carlo techniques that amplify to zero error through repetition, though it aligns more closely with Las Vegas models in practice.^[26] These classes relate hierarchically as P ⊆ ZPP ⊆ RP ⊆ BPP ⊆ PSPACE, where P denotes deterministic polynomial time and PSPACE polynomial space.^[29]^[30] The inclusion BPP ⊆ PSPACE follows from simulating probabilistic machines deterministically by enumerating all polynomial-length random strings using polynomial space.^[30] Open questions persist, such as whether BPP equals P, reflecting ongoing uncertainty about the power of bounded randomness.^[31]

Monte Carlo versus Las Vegas Algorithms

Las Vegas algorithms are a class of randomized algorithms that always produce the correct output, though their running time is variable and only guaranteed to be polynomial in expectation, with zero probability of error.^[32] In contrast, Monte Carlo algorithms operate within a fixed polynomial time bound but permit a small, bounded probability of error in their output.^[33] The primary distinction lies in their error handling and runtime guarantees: Monte Carlo algorithms trade potential inaccuracies for deterministic time complexity, making them suitable for scenarios where approximation suffices, whereas Las Vegas algorithms prioritize absolute correctness at the expense of possibly extended execution times due to randomization.^[34] This difference arises because Las Vegas methods may retry or loop until a valid solution is found, while Monte Carlo approaches accept the risk of failure within their time limit.^[35] In terms of complexity classes, Monte Carlo algorithms align with RP for one-sided error and BPP for two-sided error, while Las Vegas algorithms correspond to ZPP.^[5] A representative example of a Las Vegas algorithm is randomized quicksort, which selects pivots randomly to ensure expected linearithmic time for sorting while always yielding the correct order.^[34] By comparison, a Monte Carlo approach might be used for approximate counting problems, such as estimating the number of satisfying assignments in a Boolean formula via random sampling, where the output is accurate within a multiplicative factor with high probability but fixed runtime.^[36] The trade-offs favor Monte Carlo algorithms for tackling computationally hard problems efficiently when exact solutions are impractical, as they provide reliable approximations quickly; Las Vegas algorithms are preferred in contexts demanding guaranteed exactness, despite the variability in performance.^[6]

Applications

Computational Number Theory

Monte Carlo algorithms have found significant application in computational number theory, particularly for solving problems that are intractable with deterministic methods of comparable efficiency. One prominent area is primality testing, where probabilistic approaches enable rapid verification of large integers' primality with high confidence. The Solovay-Strassen algorithm, proposed in 1977, serves as an early example of such a Monte Carlo method. It tests whether an odd integer n > 2 is prime by selecting random bases a from 1 to n-1 and verifying if the Jacobi symbol (a/n) equals a^{(n-1)/2} \mod n. If n is prime, the test always passes; if composite, it fails with probability at most $1/2 per trial, exhibiting one-sided error where primes are never misclassified.^[37] The Miller-Rabin algorithm, originally formulated in 1976 under the generalized Riemann hypothesis and later adapted into a fully probabilistic version in 1980, builds on similar principles but uses Fermat's little theorem and strong pseudoprimality. For an odd integer n > 2 written as n-1 = 2^s d with d odd, the test selects random bases a and checks a sequence of conditions: compute x = a^d \mod n, and if x \neq 1 and x \neq -1, square repeatedly up to $2^{s-1} times to verify if -1 appears or if the initial x = 1. Primes always pass, while composites fail with probability exceeding $3/4 per witness, ensuring one-sided error.^[38]^[39] In Miller-Rabin, the witnesses are the bases a that detect compositeness. Running the test with k independent random witnesses reduces the error probability such that the chance a composite n is declared prime satisfies

\Pr[\text{composite declared prime}] \leq 4^{-k}.

This bound arises from the fact that at most $1/4 of possible bases are non-witnesses for any composite n. The algorithm's efficiency—polynomial time per trial—makes it suitable for cryptographic applications, where it is implemented in libraries like OpenSSL for testing large primes with negligible error after sufficient iterations, typically k = 40 or more for 2048-bit numbers.^[39]^[40] Beyond primality, Monte Carlo methods aid integer factorization. Dixon's method, introduced in 1981, employs random selection to find factors of a composite n. It generates random integers x_i near \sqrt{n}, smooths their values modulo n by trial division against a factor base of small primes, and collects relations until a subset's product is a square modulo n, yielding a non-trivial factor via gcd computation. The approach is probabilistic, relying on random x_i to produce enough smooth relations, with expected subexponential time complexity L_n(1/2, \sqrt{2}), where L_n(a,c) = e^{c (\ln n)^a (\ln \ln n)^{1-a}}. This laid groundwork for advanced factoring like the quadratic sieve.^[41] For the discrete logarithm problem in cyclic groups, such as finding \log_g h modulo a prime p, Pollard's rho method, extended in 1978, uses a Monte Carlo strategy with controlled error bounds. It defines a pseudorandom walk on the group via a polynomial iteration x_{i+1} = x_i^2 + c \mod p (or variants), tracking pairs (x_i, y_i) in two phases to detect collisions where x_i \equiv y_j \mod p but exponents differ, solving for the log via discrete log in a small subgroup. The birthday paradox ensures a collision in expected O(\sqrt{p}) steps, with failure probability bounded by tuning the walk and retries, making it a practical heuristic despite potential cycles.^[42]

Other Domains

Monte Carlo algorithms find extensive application in optimization problems, particularly for tackling NP-hard challenges where exhaustive search is infeasible. Simulated annealing, a probabilistic technique inspired by the annealing process in metallurgy, employs Monte Carlo sampling to explore the solution space by accepting worse solutions with a probability that decreases over time, enabling escape from local optima and convergence toward global minima. Introduced by Kirkpatrick et al. in 1983, this method has been widely used for combinatorial optimization tasks such as circuit design and traveling salesman problems. Similarly, genetic algorithms leverage Monte Carlo-style random sampling in their selection, crossover, and mutation operations to evolve populations of candidate solutions, facilitating global optimization in complex, high-dimensional landscapes like protein folding or scheduling. Hybrids combining genetic algorithms with Monte Carlo simulations further enhance robustness by incorporating stochastic evaluations to handle uncertainty in objective functions.^[43]^[44] In physics and simulation, Monte Carlo methods are pivotal for estimating high-dimensional integrals that arise in theoretical models. In particle physics, lattice quantum chromodynamics (QCD) simulations use Monte Carlo importance sampling to compute non-perturbative effects, such as hadron masses and decay constants, by generating configurations of quark and gluon fields on a discrete spacetime lattice. These techniques, essential since the 1980s, allow numerical evaluation of path integrals intractable analytically, providing predictions that align with experimental data from accelerators like the LHC. In financial modeling, Monte Carlo simulations approximate option prices under the Black-Scholes framework by generating thousands of random paths for the underlying asset, discounting the expected payoff to yield the fair value; this approach, pioneered by Boyle in 1977, excels for path-dependent derivatives where closed-form solutions fail.^[45]^[46] Machine learning benefits from Monte Carlo algorithms in probabilistic modeling, especially for Bayesian inference where posterior distributions are complex. Markov Chain Monte Carlo (MCMC) methods, such as the Gibbs sampler, generate samples from these posteriors by constructing Markov chains that converge to the target distribution, enabling parameter estimation in hierarchical models like Gaussian processes or topic models. Gelfand and Smith (1990) demonstrated MCMC's utility for marginal density computation, revolutionizing scalable Bayesian computation in fields from epidemiology to image analysis. A notable application is the approximation of volumes of convex bodies, where the Dyer-Frieze-Kannan algorithm (1991) uses randomized walks and Monte Carlo integration to achieve a polynomial-time estimate with relative error guarantees, impacting computational geometry and optimization. In artificial intelligence, Monte Carlo Tree Search (MCTS) combines tree expansion with random playouts to evaluate game states; in AlphaGo, Silver et al. (2016) integrated MCTS with neural networks for move selection, achieving superhuman performance in Go by balancing exploration and exploitation through simulated trajectories.^[47]^[48]^[49]

References

[1]
What Is Monte Carlo Simulation? - IBM
Monte Carlo Simulation is a type of computational algorithm that uses repeated random sampling to obtain the likelihood of a range of results of occurring.
[2]
Introduction To Monte Carlo Simulation - PMC - PubMed Central
Jan 1, 2011 · This paper reviews the history and principles of Monte Carlo simulation, emphasizing techniques commonly used in the simulation of medical imaging.
[3]
[PDF] Monte Carlo Methods: Early History and The Basics
Other Early Monte Carlo Applications. ▻ Numerical linear algebra based on sums: S = P. N i=1 ai. 1. Define pi ≥ 0 as the probability of choosing index i, with.Missing: scholarly | Show results with:scholarly
[4]
Hitting the Jackpot: The Birth of the Monte Carlo Method | LANL
Nov 1, 2023 · Learn the origin of the Monte Carlo Method, a risk calculation method that was first used to calculate neutron diffusion paths for the ...Missing: algorithm definition scholarly
[5]
Monte Carlo Simulation - an overview | ScienceDirect Topics
Monte Carlo simulation is a computerized technique using repeated sampling and probability to analyze decision outcomes and assess risk and uncertainty.<|control11|><|separator|>
[6]
[PDF] Randomized Algorithms and Probabilistic Analysis Lecture #1 ...
The class of problems that have polynomial-time 2-sided error Monte Carlo algorithms is known as “BPP” (Bounded Error Probabilistic Polynomial). The ...
[7]
[PDF] 22 Monte Carlo Randomized Algorithms
A Monte Carlo algorithm typically runs in a fixed amount of time, where the runtime is typically independent of the random choices made. However, it only ...Missing: characteristics | Show results with:characteristics
[8]
[PDF] The Power of Randomness - Harvard SEAS
Note that the error probability of an RP algorithm can be reduced to 2−p(n) for any polynomial p by running the algorithm p(n) times independently and accepting.
[9]
[PDF] Lecture 11: Randomization and Complexity - Washington
Feb 10, 2016 · 2-sided error: The probability the algorithm is correct is bounded away from 1/2, for example with probability ≥ 2/3. • 1-sided error: The ...
[10]
[PDF] The Monte Carlo Method - Texas A&M University
The DNF counting algorithm II is a fully polynomial randomized approximation scheme for the DNF counting problem when ... time polynomial in lnp1{q and the size ...<|control11|><|separator|>
[11]
[PDF] Stan Ulam, John von Neumann, and the Monte Carlo Method
T he Monte Carlo method is a sta- tistical sampling technique that over the years has been applied successfully to a vast number of scientific problems.
[12]
The Monte Carlo Method - Taylor & Francis Online
Journal of the American Statistical Association Volume 44, 1949 - Issue 247 ... The Monte Carlo Method. Nicholas Metropolis Los Alamos Laboratory. &. S. Ulam ...
[13]
[PDF] The History of the Monte Carlo Methods
Monte Carlo went on to be named one of the top 10 algorithms of. 20th century. “Given the digital computer's reputation for deterministic calculation, it's ...
[14]
[PDF] Turing and the Development of Computational Complexity
Aug 24, 2011 · Awardees who we have cited in this paper include Manuel Blum, Stephen Cook, Juris Hartmanis,. Richard Karp, Michael Rabin, Dana Scott, Richard ...
[15]
[PDF] AN OVERVIEW OF COMPUTATIONAL COMPLEXITY
Rabin suggested an axiomatic framework that provided the basis for the abstract complexity theory developed by Blum [6] and others. A second early (1965) ...Missing: Manuel | Show results with:Manuel
[16]
[PDF] A Short History of Computational Complexity - Gwern
Oct 2, 2003 · In the 70's we saw the growth of complexity classes as researchers tried to encompass different models of computations. One of those models, ...
[17]
[PDF] Progress in Computational Complexity Theory - cs.wisc.edu
Feb 17, 2006 · In the mid 1970s, a pair of algorithms, one due to Solovay and Strassen [62], and one due to Rabin [53] based on an earlier algorithm of Gary ...
[18]
One-sided versus two-sided error in probabilistic computation
We demonstrate how to use Lautemann's proof that BPP is in Σ 2 p to exhibit that BPP is in RP PromiseRP. Immediate consequences show that if PromiseRP is easy.
[19]
[PDF] Chernoff Inequalities - Texas A&M University
Let A be a randomized algorithm that decides L P BPP. Let us construct an algorithm A1 that runs A on an input x precisely n times and returns the majority vote ...
[20]
[PDF] Chapter 13 - Randomized Algorithms - cs.Princeton
[Monte Carlo] Decision problems solvable with one-sided error in poly-time. One-sided error. □. If the correct answer is no, always return no.
[21]
[PDF] Lecture 11 1 Overview 2 BPP Amplification - People | MIT CSAIL
Mar 14, 2007 · This lecture describes BPP amplification, shows BPP ⊂ P /poly, and shows that BPP is contained within the polynomial hierarchy. Finally, we have ...
[22]
[PDF] 1 Chernoff Bound 2 - cs.Princeton
Chernoff Bound 2 states for independent variables 0 ≤ Xi ≤ 1, Pr[X ≥ (1 + )µ] ≤ exp − 2 2 + µ and Pr[X ≤ (1 − )µ] ≤ exp − 2 2 µ.Missing: amplification BPP
[23]
[PDF] Amplification and Derandomization Without Slowdown
Mar 31, 2016 · By the Chernoff bound, the error probability of algorithm B can be made less than 2−n. By a union bound over all 2n inputs, we see that there.
[24]
[PDF] Notes on Primality Testing And Public Key Cryptography Part 1
The Solovay–Strassen Test. 6.1 Quadratic Residues. The Solovay–Strassen primality test was published in 1977, and thus slightly predates the. Miller–Rabin test.<|control11|><|separator|>
[25]
[PDF] Solovay-Strassen test - Keith Conrad
Historically, the Solovay–Strassen test was the first probabilistic primality test. The. Fermat test is not a probabilistic primality test because Carmichael ...
[26]
[PDF] 2.1 Complexity Classes
Sep 15, 2004 · In this lecture we will look at some randomized complexity classes: RP, co−RP, ZPP, and BPP. We begin with a (very brief) review of P and NP ...
[27]
[PDF] arXiv:1411.0628v20 [cs.CC] 2 Nov 2022
Nov 2, 2022 · BPP (bounded-error probabilistic polynomial time) is the class of decision problems solvable by a proba- bilistic Turing machine in polynomial ...
[28]
[PDF] Chapter 34 Complexity classes
2. A Monte Carlo algorithm is a randomized algorithm that might output an incor- rect result. However, the probability of error can be diminished by repeated ...
[29]
[PDF] Handout 7 1 More on Randomized Complexity Classes
Summarizing what we have so far: P ⊆ ZPP ⊆ RP ⊆ BPP. However (somewhat surprisingly), it is currently believed that P = BPP. RP,coRP,BPP, and ZPP represent ...
[30]
[PDF] Probabilistic Computation - BPP and RP
BPP ⊆ PSPACE, since using polynomial space we can deterministically simulate a BPP machine by iterating through all possible random seeds.
[31]
[PDF] Computational Complexity: A Modern Approach - Princeton University
Jan 8, 2007 · Papers by von. Neumann [?] and de Leeuw et al. [?] describe probabilistic Turing machines. The definitions of. BPP, RP and ZPP are from Gill [?] ...<|separator|>
[32]
[PDF] Las Vegas and Monte Carlo Algorithms - Duke Computer Science
Mar 22, 2016 · A randomized algorithm is called a Las Vegas algorithm if it always returns the correct answer, but its runtime bounds hold only in expectation.
[33]
[PDF] Lecture 18 18.1 Randomized Algorithms 18.2 Short probability review
In this lecture we looked at two types of randomized algorithms: • Las Vegas: A Las Vegas algorithm is always correct, but its running time is a random variable ...
[34]
RandomizedAlgorithms
These are the (polynomial-time) Monte Carlo algorithms: if our machine answers 0 or 1, we can guess whether x∈L or not, but we can't be sure. The class PP ( ...
[35]
[PDF] April 9 3.1 Kinds of randomization in algorithms 3.2 Inequalities and ...
Unlike Monte Carlo algorithms, Las Vegas Algorithms always produce the correct answer. However, this comes at the price of the running time: rather than ...
[36]
[PDF] Lecture Note 5 5.1 Approximate Counting via Basic Monte Carlo 5.2 ...
In this lecture we look at some basic approximate counting algorithms based on the classical Monte Carlo method. It is rare that simple methods like this ...
[37]
A Fast Monte-Carlo Test for Primality
COMPUT. Vol. 6,No. 1, March 1977. A FAST MONTE-CARLO TEST FOR PRIMALITY*. R. SOLOVAY'I" AND V. STRASSEN:I: Abstract, Let n be an odd integer. Take a random ...
[38]
[PDF] Riemann's Hypothesis and Tests for
INTRODUCTION. Two classic computational problems are finding efficient for: (1) testing primality (deciding whether an integer is prime or composite), ...
[39]
Probabilistic algorithm for testing primality - ScienceDirect.com
We present a practical probabilistic algorithm for testing large numbers of arbitrary form for primality.Missing: 1970s | Show results with:1970s
[40]
[PDF] the miller–rabin test - keith conrad
Introduction. The Miller–Rabin test is the most widely used probabilistic primality test. For odd composite n > 1, over 75% of numbers from to 2 to n−1 are ...
[41]
[PDF] Asymptotically Fast Factorization of Integers - cs.wisc.edu
Asymptotically Fast Factorization of Integers. By John D. Dixon*. Abstract. The paper describes a "probabilistic algorithm" for finding a factor of any large.Missing: original | Show results with:original
[42]
Monte Carlo Methods for Index Computation (mod p)
A Rho Method for Index Computation. The concept of a random mapping of a finite set is used by Knuth [1, pp. 7-8] to explain the behavior of a type of.
[43]
[PDF] Optimization by Simulated Annealing S. Kirkpatrick - Stat@Duke
Nov 5, 2007 · Each of the two chips (with about 2500 circuits) would need 3000 pins. The other distributions in Fig. 1 show the results of simulated annealing ...
[44]
A Genetic Algorithm Integrated with Monte Carlo Simulation for the ...
This paper aims at presenting a Monte Carlo simulation integrated with a genetic algorithm that addresses this stochastic nature of the problem.
[45]
[PDF] 17. Lattice Quantum Chromodynamics - Particle Data Group
Jun 1, 2020 · The statistical error is due to the use of Monte Carlo importance sampling to evaluate the path integral (a method discussed below). There are, ...
[46]
Options: A Monte Carlo approach - ScienceDirect.com
This paper develops a Monte Carlo simulation method for solving option valuation problems. The method simulates the process generating the returns on the ...
[47]
Sampling-Based Approaches to Calculating Marginal Densities
In particular, the relevance of the approaches to calculating Bayesian posterior densities for a variety of structured models will be discussed and illustrated.
[48]
Random Polynomial-Time Algorithm for Approximating Convex Bodies
A randomized polynomial-time algorithm for approximating the volume of a convex body K in n-dimensional Euclidean space is presented.
[49]
Mastering the game of Go with deep neural networks and tree search
Jan 27, 2016 · We have introduced a new search algorithm that successfully combines neural network evaluations with Monte Carlo rollouts. Our program AlphaGo ...