CSC 363 — Assignment 4
Due Monday, April 8th, 5:00pm
To avoid suspicions of plagiarism: at the beginning of your submission, clearly state any resources
(people, print, electronic) outside the course and lecture notes, that you consulted.
Answer each question completely, always justifying your claims and reasoning. Your solution will be graded not only on correctness, but also on clarity. Answers that are technically correct but that are hard to understand may not receive full marks. Mark values for each question are contained in the [square brackets].
I will be in my office all Monday afternoon (on the 8th) or you can put the assignment in my mailbox in DH 3008.
1. Given m identical machines, and a set of n jobs J, where each job has a size si, you’re tasked with determining if a reasonable schedule exists. A schedule is an assignment of the jobs to machines. A single job is assigned to a single machine. The load on a machine is the sum of all the sizes of the jobs assigned to that machine. The makespan of a schedule is the largest load across all machines. A schedule is reasonable if the makespan of that schedule is less than or equal to some constant k, where k is given. This problem can be given as a language, such as:
Job Scheduling = {< J, m, k > | J can be scheduled such that the makespan ≤ k} Prove that Job Scheduling is NP-complete. You may use another NP-complete problem
seen in lecture or tutorial for your reduction. [10]
SOL:
(a) Show Job Scheduling is in NP. Given a potential schedule, one could check in poly- nomial time if the schedule is valid (all jobs are accounted for and no new jobs are added), and the makespan is less than or equal to k.
(b) Show Partition ≤P Job Scheduling. Given a set of integers S determine if there’s a partition of that set in polynomial time given access to a constant time black box solution to Job Scheduling. Let J = S (the integers are the sizes of the jobs), m = 2, and k = s/2 where s is the sum of S. Then ask if fJS(J,m,s). fJS(J,m,s) will return yes iff there is a Partition of S. That is, if there’s a partition of S, then split the jobs as that partition to achieve a makespan of s/2. Furthermore, if there a makespan of s/2, one of the machines has a load of s/2, which means the other machine has a load s − s/2 = s/2, which means there’s a Partition.
2. Let MIXED = {M | M halts on at least one input, and M loops on at least one input}. Prove MIXED is NP-hard. [10]
SOL: Show 3-SAT ≤P MIXED.
1
2 Given a φ, determine it’s satisfiable in polynomial time given access to a a black box
solution to MIXED. Create a machine M, such that:
M(x) = set x aside, and brute force determine if \phi is satisfiable
if it is:
if x == 0: #note, the choice of 0 is arbitrary here
accept
else: loop
else: accept
Then by construction M ∈ MIXED iff φ is satisfiable. Therefore, just ask the blackbox fMIXED(M).