Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
COMP 3804 — Assignment
Assignment Policy:
• Your assignment must be submitted as one single PDF file through cuLearn.
Use the following format to name your file:
LastName StudentId a4.pdf
• Late assignments will not be accepted. I will not reply to emails of the
type “my internet connection broke down at 23:57” or “my scanner stopped
working at 23:58”, or “my dog ate my laptop charger”.
• You are encouraged to collaborate on assignments, but at the level of discussion only.
When writing your solutions, you must do so in your own words.
• Past experience has shown conclusively that those who do not put adequate effort into
the assignments do not learn the material and have a probability near 1 of doing poorly
on the exams.
• When writing your solutions, you must follow the guidelines below.
– You must justify your answers.
– The answers should be concise, clear and neat.
– When presenting proofs, every step should be justified.
Question 1: Write your name and student number.
Question 2: The (0, 1)-integer programming problem is defined as follows:
IntProg := {(A, c) : A is an integer m× n matrix for some integers m and n,
c is an integer vector of length m, and
∃x ∈ {0, 1}n such that Ax ≤ c (componentwise) }.
Prove that the language IntProg is in NP.
1
Question 3: The subset sum problem is defined as follows:
SubsetSum := {(a1, a2, . . . , am, b) : m, a1, a2, . . . , am, b are integers and
∃I ⊆ {1, 2, . . . ,m} such that ∑i∈I ai = b}.
Prove that SubsetSum ≤P IntProg, i.e., in polynomial time, SubsetSum can be reduced
to IntProg.
Question 4: The three-coloring problem is defined as follows:
3Color := {G : G is a graph whose vertices can be colored using three colors
such that any two adjacent vertices have distinct colors }.
The clique covering problem is defined as follows:
CliqueCover := {(G, k) : G = (V,E) is a graph whose vertex set V can be
partitioned into k subsets V1, V2, . . . , Vk such that
each subset Vi forms a clique in G }.
(4.1) Prove that the language 3Color is in NP.
(4.2) Prove that the language CliqueCover is in NP.
(4.3) Prove that 3Color ≤P CliqueCover, i.e., in polynomial time, 3Color can be
reduced to CliqueCover.
Question 5: You are given
• a sequence A = (A1, A2, . . . , Ak), where each Ai is a set consisting of three elements,
and
• a sequence B = (B1, B2, . . . , B`), where each Bj is a set consisting of two elements.
This pair (A,B) of sequences is called good if there exists a set T such that
• T contains at least one element of each set Ai, and
• T contains at most one element of each set Bj.
The Problem without a Name is defined as follows:
ProblemWithoutAName := {(A,B) : the pair (A,B) is good}.
Prove that the language ProblemWithoutAName is NP-complete.
Hint: You may remember from class that 3Sat is NP-complete.