COMP3630/6360: Theory of Computation Semester 1, 2022
The Australian National University
Probabilistic Computation and Approximation
Copyright By PowCoder代写 加微信 powcoder
The Conundrum
We need to solve an NP-complete problem. What can we do?
Approaches
If a problem is NP-complete (or worse . . . )
Hope that we need to deal with small instances only Hope that we don’t need to deal with all instances
instances we need to deal with might have extra structure
Don’t insist on the best solution
Don’t insist on getting it right all the time.
VERTEX-COVER
If G = (V,E) is an undirected graph, a vertex cover of G is a subset C ⊆ V where every edge touches one of the nodes in C:
Theorem 1.1
The problem
∀(x , y ) ∈ E (x ∈ C ∨ y ∈ C )
VERTEX-COVER = { ⟨G,k⟩ | G has a k-node vertex cover } is NP-complete.
We show 3SAT ≤P VERTEX-COVER by transforming 3cnf-formulas into undirected graphs with 2 nodes per variable and 3 nodes per clause. [Details: see Sipser]
An NP-completeness proof is typically the first act of the analysis of a computa- tional problem by the methods of the theory of algorithms and complexity, not the last. Once NP-completeness has been established, we are motivated to explore possibilities that are less ambitious than solving the problem exactly, efficiently, every time.
(Papadimitriou 1994, Page 299)
Optimisation Problems
In optimisation problems we seek the best solution among a collection of possible solutions.
Example 1.2
On input ⟨G⟩, where G is an undirected graph, find a smallest vertex cover. This is NP-hard, too. (We did not formalise this notion.)
Approximation Algorithms
Apx = “On input ⟨(V,E)⟩, where (V,E) is an undirected graph:
1 Set M := ∅.
2 While there exists an edge (x, y) ∈ E ∩ M2
1 M := M ∪ {x,y} — add both vertices to the cover
2 V:=V\{x,y};E:=E∩(V×V)—removethevertices
3 Output ⟨M⟩”.
arguably generates some vertex cover for (V,E) in polynomial time. But how close is it to an optimal one?
Theorem 1.3
Apx produces a vertex cover no more than twice as large as a smallest one.
Correctness: With every pair of nodes removed in the body of the main loop, we add both nodes to the cover. This implies that when we then remove these nodes from the graph, all edges removed touch a node in the cover.
Approximation: For each pair of nodes removed by an iteration of Apx’s main loop, a smallest vertex cover would contain at least one of the removed nodes, otherwise the edge between them wouldn’t be covered.
k -Optimality
Definition 1.4
An approximation algorithm for a minimisation problem is k-optimal if it always finds a solution that is at most k times the size of an optimal one.
An approximation algorithm for a maximisation problem is k-optimal if it always finds a solution that is at least k1 times the size of an optimal one.
Example 1.5
We’ve just shown that Apx is 2-optimal for VERTEX-COVER.
Traveling Salesman Problem
Given n cities 1, . . . , n, and a nonnegative symmetric integer distance di ,j = dj ,i between any two cities i and j, we’re asked to find the shortest tour of the cities—that is, a permutation π such that ni=1 dπ(i),π((i mod n)+1) is minimal. This problem is called TSP.
Theorem 1.6
Unless P = NP, there is no k ∈ N for which there exists a k-optimal approximation algorithm for TSP.
Suppose to the contrary that T is k-optimal for TSP. Then we can use T to solve HAMCYCLE (undirected HAMPATH with a closing edge) in P by the machine
H = “On input ⟨(V,E)⟩, where (V,E) is an undirected graph:
1 Run T on a TSP instance with |V| nodes and distances di,j =
2 If T returns a total cost of |V | then accept, otherwise reject.”
if (i,j) ∈ E otherwise
This looks bad. If however all distances satisfy the triangle inequality, di ,j + dj ,k ≥ di ,k , there are 23 -optimal approximation algorithms.
Probabilistic Algorithms
Definition 1.7
A probabilistic TM (PTM) M is a type of NTM in which each non-deterministic step is called a coin-flip step and has two legal next moves.
The probability of branch b of M’s computation on input w is
Pr[b]= 1 2k
where k is the number of coin-flip steps that occur on b. The probability that M accepts/rejects w is
Pr[Macceptsw]= Pr[b] b accepts w
Pr[M rejects w] = 1 − Pr[M accepts w]
Definition 1.8
For ε ∈ [0, 12 ) PTM M recognises A with error probability ε if
1 w ∈ A implies Pr[M accepts w] ≥ 1 − ε, and
2 w ∈/ A implies Pr[M rejects w] ≥ 1 − ε.
BPP is the class of languages that are recognised by polynomial time PTMs with an error probability of 31 .
Amplification Lemma
The definition of BPP is robust w.r.t. the choice of error probability; 13 is just one convenient possiblity in [0, 12 ).
Let ε ∈ [0, 12 ) and k > 0.
If polynomial time PTM M recognises A with error probability ε then there is another
polynomial time PTM M′ that also recognises A with error probability 1 . 2nk
Run M more than once on the input word and take a majority vote among the outcomes.
Since 2002, we know that
PRIMES={n| nisaprimenumberinbinary}
is in P (e.g. O(log10.5 n)), contrary to what many had believed till then. We’ll study a (relatively simpler) proof of PRIMES ∈ BPP.
This requires a tiny bit of good old-fashioned number theory.
LetZp ={0,…,p−1}andZ+p =Zp \{0}.
Theorem 2.1 (Fermat’s little theorem, 1640)
Ifpisaprimeanda∈Z+p thenap−1 ≡1modp. Proof from wikipedia.org.
Consider all the possible strings of p symbols, using an alphabet Σ with a different symbols. The total number of such strings is |Σ|p = ap.
The bracelet of such a word w1 …wp is the set of words
w(1+k)%p …w(p+k)%p | k ∈ Zp .
The bracelets form a partition of Σp. The bracelet of a word bp for b ∈ Σ is the singleton set {bp}. All other bracelets have size p.
It follows that ap − a = a(ap−1 − 1) is divisible by p. Since a and p are co-prime, ap−1 − 1 must also be divisible by p. The claim follows.
Definition 2.2
p passes the Fermat test at a if ap−1 ≡ 1 mod p.
A pseudoprime is a number p that passes Fermat tests for all smaller co-primes a.
If p isn’t pseudoprime it fails at least half of its Fermat tests.
A probabilistic algorithm for pseudoprimality would, on input p,
1 Selecta1,…,ak ∈Z+p randomly.
2 Compute ap−1 % p for each i. i
3 If all computed values are 1, accept, otherwise, reject. Parameter k affects the error probability: it is at most 1 .
Pseudo-primes that aren’t primes are called Carmichael numbers and quite rare, e.g. 561,
1105, 1729, 2465,. . .
What can we do about them?
Saythatqisasquarerootof1modulopifq2 ≡1modp. If p is prime then only ±1 are square roots of 1 modulo p.
For many composite numbers, including all the Carmichael numbers, 1 has 4 or more such square roots.
Examples 2.3
±1, ±8 are the square roots of 1 modulo 21.
±67, ±188, ±254 are the square roots of 1 modulo 561.
Could we test for these square roots?
After passing the Fermat test ap−1 ≡ 1 mod p we deduce that the number a(p−1)/2 % p
is a square root of 1 modulo p. We continue to half the exponent as long as it is even, checking whether the first different value is −1. If it is a different number, then 1 has a square root modulo p that is different from ±1, hence p is no prime.
BPP Algorithm for PRIMES
prime = “On input p:
1 If p is even, accept if p = 2; otherwise, reject. 2 Selecta1,…,ak ∈Z+p randomly.
3 For each 1 ≤ i ≤ k:
1 Compute ap−1 % p and reject if different from 1. i
2 Lets,t,h∈Nsuchthats·t=p−1wheresisoddandt=2h. 3 Computethebi,j =as·2j %pfor0≤j≤h.
4 Reject if for the greatest j with bi,j ̸= 1 also bi,j ̸= −1.
4 Accept.”
If p is a prime number then Pr[prime accepts p] = 1.
If p is an even composite number then Pr[prime accepts p] = 0.
If p is an odd composite number then Pr[prime accepts p] ≤ 1 . 2k
For details see [Sipser2006]. We also use that modular exponentiation is in P for
Theorem 2.4
PRIMES ∈ BPP.
prime has an interesting property: its error is one-sided. Any rejected number must be composite (i.e. the error probability when rejecting is 0) whereas there is a small probability that an accepted number is not prime.
Definition 2.5
RP is the class of languages that are recognisable by probabilistic polynomial time TMs where inputs in the language are accepted with a probability of at least 12 and inputs not in the language are rejected with a probability of 1.
Corollary 2.6
COMPOSITES = PRIMES ∈ RP.
Monte- 3.1
Call a probabilistic TM Monte-Carlo if it accepts any given word w with probability of either 0 (i.e. rejection is guaranteed) or ≥ 21 .
Corollary 3.2
RP is the set of languages of P-time Monte- Ms.
It is an open problem whether RP =? coRP.
Corollary 3.3
1 RP ⊆ BPP
2 RP ⊆ NP (and hence coRP ⊆ coNP)
So far we’ve always categorised time complexities based on the worst-case running time. Differences may arise if we move to expected running time.
Definition 3.4
Call a probabilistic TM Las Vegas if it accepts and rejects with certainty but its running time may vary with the probabilitic choices made.
Obviously, every (deterministic) TM is a Las Vegas TM.
Definition 3.5
Let ZPP (for zero-error, probabilistic, polynomial) be the class of languages recognised by (expected) P-time Las Vegas TMs.
Example 3.6
That PRIMES ∈ ZPP has been known since 1987, predating the seminal proof of PRIMES ∈ P.
Corollary 3.7
2 A ∈ ZPP ⇒ A ∈ ZPP (so we needn’t define coZPP)
1. Let A ∈ P. By definition of P there exists k ∈ N and a TM M such that L(M) = A and, for all words w, the running time of M on w never exceeds |w|k. There is only one computation path per input word to consider, so the weighted average over all computation paths is equal to the running time on the unique computation path. Thus we may use M as an expected P-time Las Vegas TM recognising A.
2. Las Vegas machines never lie (but they may take longer to answer than you’re prepared to wait). Therefore we can flip qaccept and qreject to recognise complements without affecting expected P-time.
ZPP vs. RP
Theorem 3.8
ZPP = RP ∩ coRP
Compare this to the open problem of P =? NP ∩ coNP.
ProofofZPP⊇RP∩coRP:LetA∈RP∩coRP.LetMandM′ beMonteCarloTMs with L(M) = A = L(M′).
Las Vegas TM N = “On input w:
1 Run M on w. If M accepts, accept.
2 Run M′ on w. If M′ accepts, reject.
3 Repeat.”
Clearly N never gives a wrong answer. But what is its expected running time? If both M and M′ are running in at most nk time then each iteration takes about 2nk steps. The probabilty of halting in an iteration is > 12 . The expected running time of N is thus clearly polynomial:
Pr[N halts after iteration i ] · N ’s running time for i iterations i>0
1kkik ≤ 2i·i2n=2n2i≤4n
Proof of ZPP ⊆ RP ∩ coRP uses Markov’s inequality: Theorem 3.9
Any non-negative random variable X satisfies Pr(X ≥ k E[X ]) ≤ k1 . Let N be an expected nk -time Las Vegas TM with L(A).
Let A ∈ ZPP. Let Monte M M = “On input w:
1 Run N on w for at least 2|w|k steps. If it halts, give its answer; otherwise, reject.”
If w ∈/ A then N will reject with certainty.
By Markov’s inequality the chance that it will yield an answer before we stop it is ≥ 12 .
This means the chance we’ll give the wrong answer on w ∈ A by timing out, is ≤ 12 . Hence A ∈ RP.
To show A ∈ coRP use the same M but accept when timing out.
Quantum Complexity.
How does it work? How does it change? Lots of open questions . . . Average Time Complexity. (Levin, 1986)
what’s a good definition? What classes do we have?
Fixed Parameter Complexity
often, just some aspects of a problem contribute to complexity separate out easy / hard parameters
Complexity of Logical Formalisms
mainly automated reasoning
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com