Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

COMP 360 Fall 2023

Assignment 4

Due: Thursday, November 16th, 2023 at 8:00pm

Please submit the assignment on Crowdmark by the due date.  In all problems below where you are asked to give an efficient algorithm, you must also prove that your algorithm is correct and analyze its running time. If you use any sources other than the course textbook or the lecture notes (e.g. other textbooks, online notes, friends) please cite them for your own safety. Do not upload this assignment to any online repository. Also, a reminder that direct copying from sources is not permitted, and solutions must be in your own words.

Questions

1.  Let x1 , x2 , . . . , xn  be a  set of variables.   A polynomial  equation over these variables is an   [10] expression of the formp(x1 , x2 , . . . , xn) = 0, where pis a polynomial with rational coefficients

over the variables x1 , . . . , xn. For example, x1(2)x3 − 3x2 + 3 = 0 is a polynomial equation, as is x1x2x3 − x4x5 /2 = 0.

Consider the following problem. As input, you receive a list of polynomial equations

p1 (x1 , . . . , xn) = 0, p2 (x1 , . . . , xn) = 0, . . . , pm(x1 , . . . , xn) = 0

over the variables x1 , . . . , xn. The output is to decide if there is a boolean assignment x1 , x2 , . . . , xn  ∈ {0, 1} to the variables such that all the given polynomial equations are simultaneously satisfied.

Prove that this problem is NP-Complete.

2.  Consider the following variation of the independent set problem. Now, as input, you receive a    [10] graph G = (V, E) and a positive integer k. The goal is to decide if there is a subset of vertices

U ⊆ V such that |U | ≥ k and U contains at most 1 edge.

Prove that this problem is NP-Complete.

Figure 1: An example input for the problem in Q3, with two of the clauses highlighted.

3. Consider the following variation of the SAT problem. As input, you are given a positive integer    [10] n, along with an m × m table T. Each entry of the table contains a boolean literal T [i, j] from a fixed set of n variables x1 , x2 , . . . , xn. For any i,j with 1 ≤ i, j ≤ m − 1, we can define the clause Cij  = T [i, j] ∨ T [i + 1, j] ∨ T [i, j + 1] ∨ T [i + 1, j + 1]. See Figure 1 for an example.

The decision problem is then the following: given this table T, n, and m as input, decide if the formula

is satisfiable.

Prove that this problem is NP-Complete.

4.  Consider the following variation of the 3-Colouring Problem.  As input, you receive a graph    [10] G = (V, E) such that |V | is divisible by 6. As output, you must decide if there is a 3-colouring χ : V → {1, 2, 3} of G where, additionally, exactly 2|V |/3 vertices receive colour 1, exactly |V |/6 vertices receive colour 2, and exactly |V |/6 vertices receive colour 3.

Prove that this problem is NP-Complete.

5.  Let A and B be two decision problems with the same set of inputs.  For example, A could be    [5] the Independent Set problem and B could be the Vertex Cover problem, since the input to both problems is a pair (G, k), where G is a graph and kis a positive integer. Define the new decision problem A AND B as follows. The input to A AND B is any valid input x for A and B. The output is to decide if A(x) = “Yes” and B(x) = “Yes”. For example, in the “Independent Set AND Vertex Cover” problem, we are given a graph G and positive integer k, and must decide if G has an independent set of size ≥ kand a vertex cover of size ≤ k.

Describe two decision problems A and B with the same set of inputs such that both A and B are NP-Complete, but A AND B is computable in polynomial time.  (Hint: Take a known NP-Complete problem, and modify it so that it is still NP-Complete.)

6. Bonus. Describe two NP-Complete problems A and B such that A AND B is still NP-Complete.   [5]