COMP 400 ASSIGNMENT 5
Question 17 (14 marks)
For each of the two questions below, decide whether the answer is (i) “Yes,”
(ii)“No,” or (iii) “Unknown, because it would resolve the question of whether
P = NP.” Give a brief explanation of your answer.
(a) Recall the Interval Scheduling Problem from COMP 271: Given a collection of intervals on a timeline, and a bound k, does the collection contain a
subset of non overlapping intervals of size at least k? Can we have Interval
Scheduling ≤p Vertex Cover.
(b) Is it the case that 3-COL ≤p Interval Scheduling?
Question 18 (9 Marks)
The PARTITION problem is defined as follows: you are given a set of n positive numbers x1, . . . , xn, and you have to decide if they can be partitioned
into two sets S1 and S2 such that the sum of numbers in each of the two
sets are equal. Prove that PARTITION is NP-complete.
Question 19 (6 Marks)
Prove that the following problem belongs to P: Given a graph G, we want
to know whether G has an independent set of size 100.
Question 20 (7 Marks)
Consider the Triangle Removal Problem from Question 15. Prove that Triangle Removal Problem is NP-complete. You may assume that we have completed showing Triangle Removal Problem is in NP.
本网站支持 Alipay WeChatPay PayPal等支付方式
E-mail: email@example.com 微信号:vipnxx