Hello, if you have any need, please feel free to consult us, this is my wechat: wx91due
CS 262: Computational Complexity Homework 6
1. FP is the set of functions from {0, 1} ∗ to {0, 1} ∗ that can be computed by a deterministic Turing Machine in polynomial time. Show that computing the permanent of a matrix with integer entries can be done in FP#SAT. Note that the integer entries may be negative but you will get partial credit if you prove this under the restricion of non-negative entries.
2. The function W takes as input a graph G with integer weights on its edges. The weight of a cycle cover is the product of all the weights in the cycle cover. W(G) is the sum of the weights of all the distinct cycle covers in G. An -approximation for W is a function A such that for any weighted graph G, W(G) ≤ A(G) ≤ W(G)/. Show that if there is an , and a polynomial time algorithm that computes an -approximation of W(G), then P = NP.
3. Let IP’ be the class obtained from the definition of IP, except that we will allow the prover to also be probabilistic. That is, the prover’s strategy can be chosen at random from distribution of strategies. Show that IP’ = IP. More formally, L is the class of languages for which there is a proof system (Pr, Vr 0), where r and r 0 are random strings. Selecting r at random gives a distribution over provers and selecting r 0 at random gives a distribution over verifiers.
(a) If x ∈ L, then P robr,r0[(Pr, Vr 0)(x) accepts ] ≥ 2/3.
(b) If x 6∈ L, then for any distribution over provers P ∗ r , P robr,r0[(P ∗ r , Vr 0)(x) accepts ] ≤ 1/3.