Computer Science 4236: Introduction to Computational Complexity Problem Set #3, Spring 2022
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
Computer Science 4236: Introduction to Computational Complexity
Problem Set #3, Spring 2022
Problem 1 In this problem, you’ll show that some natural algorithmic problems involving mul- tivariate polynomials (such as computing certain mixed partial derivatives and multiple integrals) can be computationally hard.
(a) We say that a linear form L over variables x1 , . . . , xn is an expression of the form L = 
αixi where each coefficient αi is a real number.
Suppose that there is a polynomial time algorithm with the following property: given as input n linear forms L1, . . . , Ln over variables x1 , . . . , xn in which each coefficient of each Li is either 0 or 1 and real values v1 , . . . , vn , the algorithm computes the value of
… … … 
╱i
1 Li\
at the point (x1 , . . . , xn) = (v1 , . . . , vn). Show that this implies that P=NP. (Hint: Use the fact that computing the permanent of a 0/1 matrix is #P-complete.)
(b) We say that a quadratic form Q over variables x1 , . . . , xn is an expression of the form Q = 
αi,jxixj where each αi,j is a real number.
Now suppose that there is a polynomial time algorithm with the following property: given as input n quadratic forms Q1 , . . . , Qn over variables x1 , . . . , xn in which each coefficient of each Qi is either 0 or 1, the algorithm computes the value of
−11 … … … −11 ╱i
1 Qi \ dx1 … … … dxn .
Show that this implies P=NP as well. (The same hint applies.)
Problem 2 A monotone Boolean formula has only ANDs (一) and ORs (v) and contains no negations. For instance, (x1 一 x2 一 x3 ) v (x2 一 (x3 v x4 )) is a monotone Boolean formula.
The function #MON is defined as follows: on input a monotone Boolean formula, it outputs the number of satisfying assignments for the formula.
Prove that #MON is #P-complete. (Hint: Reduce from #3SAT. Given a 3CNF formula F (x1 , . . . , xn), construct two monotone formulas A and B (over a larger set of variables) such that the number of satisfying assignments to F equals the number of satisfying assignments to A minus the number of satisfying assignments to B.) Note that this reduction uses the power of oracle access more fully than the reductions we did in class, since the oracle is called more than once.
Problem 3 Recall that an independent set in a graph G is a subset S of vertices such that no edge is present between any pair of vertices in S. Let 0 < ε < 1 be any fixed constant. Suppose that A is a deterministic polynomial-time algorithm which, given an n-node graph G as input, outputs a
value N such that
I(G) 尸 N 尸 2n1 −l … I(G)
where I(G) is the number of independent sets in G. Prove that if such an algorithm exists then P = NP.
Problem 4 Suppose there is a poly(n)-time algorithm A which, on input an n-variable 3CNF formula φ, outputs a “low-accuracy” relative-error estimate of the number of satisfying assignments of φ; in more detail, A outputs a number A(φ) such that
#φ
(where #φ is the number of satisfying assignments of φ).
Show that then there is an fully polynomial approximation scheme for #3CNF, i.e. an algorithm which on input an error parameter 0 < ε < 1 and a 3CNF formula φ, runs in poly(n, 1/ε) time and outputs a value N such that
(1 ← ε) … #φ 尸 N 尸 (1 + ε) … #φ.
Problem 5 You are at the beach with your young cousin, two identical buckets, and a lot of sand. Your curious cousin fills one of the buckets with sand and says “I wonder how many grains of sand are in this bucket.”
Describe how you can efficiently come up with a “pretty accurate” estimate of the number of grains of sand in the bucket. (Your solution should be one that can be carried out by someone with normal human capabilities of manipulating sand and buckets, comparing the relative sizes of two objects, etc - it should not require one to be extraordinarily good at subitizing.) Explain why your procedure is pretty accurate and come up with an estimate upper bounding the worst-case multiplicative error of your procedure.
(The solution to this problem will explain its relevance to complexity theory.)
2022-04-15