0017 Computational Complexity problem sheet 8.
1. Define the following:
(a) The Travelling Salesman Problem (TSP)
(b) The Travelling Salesman Decision Problem (TSDP). Solution:
Copyright By PowCoder代写 加微信 powcoder
(a) Given a complete and undirected graph G = (V, E), and a function w : E → N, the TSP asks us to find the minimum weight of a circuit covering each node of G exactly once.
More precisely, a circuit of weight n ∈ N is defined as a sequence of pairwise distinct v0, . . . , v|V |−1 ∈ V where
w(v0, v1) + · · · + w(v|V |−2, v|V |−1) + w(v|V |−1, v0) = n
We should minimize n ∈ N such that a circuit of weight n exists.
(b) An instance of the TSDP is (G,w,d) where G = (V,E) is a complete and undirected graph and w : E → N is a function, and d is a non-negative integer. It is a yes-instance if there is a circuit of weight d or less (as in the above); otherwise, it is a no-instance. Equivalently, (G, w, d) is a yes-instance of the TSDP if and only if the solution to the TSP for (G, w) as defined above is at most d.
2. Assuming a binary encoding of all non-negative integers, give an upper bound of the size of an instance (G,w,d) of TSDP, in terms of the number of nodes (k) of the graph G, the maximum edge weight (m) of all edges and the threshhold value d.
Solution: For every pair of nodes, we should record the weight of that edge; for each of these values, we are going to need ⌈log2(m)⌉ bits. Since the input is an undirected graph, the order of the nodes does not matter; this means we have 12 × k × (k − 1) such values to keep track of. Additionally, we need ⌈log2(d)⌉ bits to record d. In total, we have:
k × (k − 1) × ⌈log2(m)⌉ + ⌈log2(d)⌉ 2
3. Let T be a deterministic TM such that T accepts w if and only if w = code(G, w, d) where (G, w, d) is a yes-instance of TSDP.
Consider the following algorithm, where the input is (G,w), with G = (V, E) a complete, undirected graph and w : E → N a function.
Answers Not to be printed
while true do
if T accepts code(G, w, d) then return d
What does this algorithm compute, and why?
Solution: This algorithm solves TSP. More precisely, when the algorithm terminates, it returns d such that (G, w, d) is a yes-instance of TSDP (i.e., there exists a circuit of total weight at most d), and moreover, for all d′ < d we have that (G, w, d′) is a no-instance (i.e., there does not exist a circuit of total weight at most d′). It then follows that d is the minimal weight of a circuit in G.
Note that this algorithm always terminates, since G is a complete graph, meaning that there exists a circuit of some total weight D, which is reached eventually by the loop (if it does not terminate before that).
4. Let f : N → N be a function such that if T (as in the previous question) receives an input of size at most n, it terminates in at most f(n) steps. In terms of the number of nodes (k) of G, the maximum edge-weight
(m) and the function f, give an upper bound on the number of steps that are performed by T in this algorithm.
Solution: Since a circuit contains exactly k edges of weight at most m, the maximum weight of a circuit is at most k × m. In the worst case, the algorithm has to let T run on all values from 0 up to k × m, and therefore calls T at most k × m + 1 times. For each of these calls, a previous exercise tells us that we have an input size of at most
S = k×(k−1) ×⌈log2(m)⌉ +⌈log2(k×m)⌉ 2
Thus, in total, T takes at most (k × m + 1) × f(S) steps.
5. In terms of the size (n) of a binary encoding of the input (G, w), and
the function f, give an upper bound on the run-time of this algorithm.
Solution: Let D be the minimum weight of a circuit in G, which exists because G is complete. We first note that D is bound from above by the sum of weights in G, and hence the number of bits in D is bound from above by n, the number of bits necessary to encode (G, w).
We need to call T with an input that encodes (G, w) as well as d; since d ≤ D, we know that the number of bits in d is bound from above by the number of bits in D, which is bound from above by n. Thus, every time we run T on an input, that input is of size at most 2n.
Answers Not to be printed
Lastly, we need to call T at most D times, and hence no more than 2n calls are made. This leads to an upper bound of 2n × f (2n).
6. Given an instance (G, w) of TSP with maximum edge weight m and number of nodes k, devise an improved algorithm to solve TSP using binary search.
Solution: Consider the following function:
Function BinarySearch(G: graph, w, d, e ∈ N): if d=ethen
return e + 1
if T accepts (G, w, g) then
return BinarySearch(G, w, d, g)
return BinarySearch(G, w, g, e)
Our algorithm calls BinarySearch(G, w, −1, m × k).
7. Give an improved upper bound on the run-time of your algorithm. You may assume that all elementary operations (e.g., checking whether d = e, for non-negative integers) take unit time.
Solution: We are running a binary search over m × k elements; it is well-known that this takes at most ⌈log2(m × k)⌉ iterations. In each of these iterations, we perform a constant number of elementary operations C (depending on what you call elementary, a pessimistic upper bound would be C = 5). This gives us a total of
⌈log2(m × k)⌉ × (C + f(S))
where S is the number of bits necessary to encode the input for a call to T, as in a previous exercise. We have also previously determined that S is at most twice as large as the number of bits necessary to encode the input, n. Since the first factor above is similarly bound from above by n, we find that we need a total of n × (C + f(2n)) steps.
Answers Not to be printed
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com