Probability and Algorithms (1992) / Chapter Skim
Currently Skimming:
4 Probabilistic Algorithms for Speedup
4 Probabilistic Algorithms for Speedup
Pages 39-52
The Chapter Skim interface presents what we've algorithmically identified as the most significant single chunk of text within every page in the chapter.
Select key terms on the right to highlight them within pages of the chapter.
From page 39... ...
Lagarias AT&T Ben Laboratories ABSTRACT This chapter surveys situations in which probabilistic algorithms offer speedup over what is possible using deterministic algorithms, either in practice or ~ e e 47 in prluclplee 4.l Introduction One of the most compelling reasons to use randomized algorithms is that they permit certain problems to be solved faster than is possible by deterministic methods. One pays a price for such speedup, which is the possibility of occasional very long computations or of occasional errors in the computation.
|
From page 40... ...
· ~ . ~ 4.2 Probabilistic Complexity Classes The theoretical possibility of speedup has been formalized in computational complexity theory with the notion of probabilistic complexity classes; these classify computational problems according to the running times and types of error allowed by probabilistic algorithms.
|
From page 41... ...
In this case, when the PPTM outputs either "x ~ [n or "x ~C", it is correct, but it is allowed to Dive no output for a small fraction of random tapes. a The complexity class BPP is closed under complementation, and we have the following inclusions shown in Figure 4.1, where P denotes the set of (deterministic)
|
From page 42... ...
The primality testing and factoring problems have the added practical significance of playing complementary roles in the RSA cryptosystem, which is the current best candidate for public key cryptography and for digital signatures. The practicality of constructing RSA ciphers depends on primality testing's being easy to do, whereas the security of the cipher depends on the apparent difficulty of factoring large numbers.
|
From page 43... ...
The primality testing problem is believed by many to be solvable in polynomial time. In fact, MiDer (1976)
|
From page 44... ...
Taken together with the SolovayStrassen result, it shows that Primes ZPP. In contrast, the fastest fully analyzed deterministic primality testing algorithm is due to Adleman et al.
|
From page 45... ...
is 1;~-smooth is about [-~/26. Dixon showed that a similar probability estimate holds for ai that are random quadratic residues Xi2.
|
From page 46... ...
can be proven rigorously (see Lenstra and Pomerance, 1992~. More recently, a new factoring algorithm, the number field sieve, has been found that incorporates probabilistic ideas and uses arithmetic in an auxiliary algebraic number field to generate x2 - y2 (mod N)
|
From page 47... ...
We describe two specific functions for which probabilistic computations give speedups. The first is the equality function equ.
|
From page 48... ...
= 1, this answer may be incorrect, with probability at most c. For the function equ, no speedup exists using a zero-error randomized algorithm (see Orlitsky and E!
|
From page 49... ...
, BPP has subexponential-time simulations unless EXP has publishable proofs, in Proc. 6th Annual Structure in Complexity Theory Conference, {EKE Computer Society Press, Los Ala~nitos, Calif., 213-219.
|
From page 50... ...
(1990) , A catalog of complexity classes, in Handbook of Theoretical Computer Science, vol.
|
From page 51... ...
, in Proc. 23rd Annual Symposium on Foundations of Computer Science, IEEE Computer Society Press, I,os Alamitos, Calif., 80-91.
|
Key Terms
This material may be derived from roughly machine-read images, and so is provided only to facilitate research.
More
information on Chapter Skim is available.