Probabilistic Computations in Complexity Theory
Explore the significance of adding probabilities to algorithms for exclusive process access, fairness considerations, and conflict resolution in computational processes like Primality testing, Hashing, Quicksort, Median Finding, and Routing in networks. Learn how probabilistic Turing machines play a role in computational complexity theory.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
CMSC 281Complexity Theory Probabilistic Computations
Probabilistic Computations Adding probabilities to algorithms is sometimes very useful Example: exclusive process access to a resource U and V want to access X and alter it(for example a file) At any point, only one of them should access it.
Probabilistic Computations Adding probabilities to algorithms is sometimes very useful Example: exclusive process access to a resource U and V want to access X and alter it(for example a file) At any point, only one of them should access it. We want to be fair. (U should not be preferred to V or vice-versa)
Probabilistic Computations Adding probabilities to algorithms is sometimes very useful Example: exclusive process access to a resource U and V want to access X and alter it(for example a file) At any point, only one of them should access it. We want to be fair. (U should not be preferred to V or vice-versa) We do not want round-robin schedule (U should not wait if V is idle)
Probabilistic Computations Adding probabilities to algorithms is sometimes very useful Example: exclusive process access to a resource U and V want to access X and alter it(for example a file) At any point, only one of them should access it. We want to be fair. (U should not be preferred to V or vice-versa) We do not want round-robin schedule (U should not wait if V is idle) If there is a conflict, toss a coin Heads let U in, T let V in. [fairness and finite wait, whp]
Probabilistic Computations Adding probabilities to algorithms is sometimes very useful Example: exclusive process access to a resource U and V want to access X and alter it(for example a file) At any point, only one of them should access it. We want to be fair. (U should not be preferred to V or vice-versa) We do not want round-robin schedule (U should not wait if V is idle) If there is a conflict, toss a coin Heads let U in, T let V in. [fairness and finite wait, whp] Pr(U has to wait t turns)=1/2t
Other examples Primality testing Hashing Quicksort Median Finding Routing in networks
Probabilistic Turing machines We also define Pr[M rejects w] = 1 Pr[M accepts w] Definition: M decides language L with error probability ? if for all w 1. If ? L then Pr[M accepts w] 1 ? 2. If ? L then Pr[M rejects w] 1 ?
Probabilistic Turing machines We also define Pr[M rejects w] = 1 Pr[M accepts w] Definition: M decides language L with error probability ? if for all w 1. If ? L then Pr[M accepts w] 1 ? 2. If ? L then Pr[M rejects w] 1 ? So if ?=1/3, strings in the language will be accepted with probability at least 2/3, and string NOT in the language will be accepted with probability at most 1/3
Probabilistic Turing machines We also define Pr[M rejects w] = 1 Pr[M accepts w] Definition: M decides language L with error probability ? if for all w 1. If ? L then Pr[M accepts w] 1 ? 2. If ? L then Pr[M rejects w] 1 ? So if ?=1/3, strings in the language will be accepted with probability at least 2/3, and string NOT in the language will be accepted with probability at most 1/3 If ?=2-n, then for long strings the chances the algorithm is wrong are negligible.
BPP BPP is the class of languages decided by probabilistic polynomial time Turing machines with error probability 1/3.
BPP BPP is the class of languages decided by probabilistic polynomial time Turing machines with error probability 1/3. The definition is robust: Nothing special about 1/3 We could have used 1 / 2 - 1/poly(n), or 1-2n
BPP BPP is the class of languages decided by probabilistic polynomial time Turing machines with error probability 1/3. The definition is robust: Nothing very special about 1/3 We could have used 1 / 2 - 1/poly(n), or 1-2n (but not 1 /2 1/2n)
BPP BPP is the class of languages decided by probabilistic polynomial time Turing machines with error probability 1/3. The definition is robust: Nothing very special about 1/3
BPP Proof idea: repeat the computation O(p(n)) times and take the majority result.
BPP Proof idea: repeat the computation O(p(n)) times and take the majority result. Easy proof using Chernoff bounds. Sipser has an elementary proof. READ IT pg 398 (& ask questions)
