NP-Completeness in Task Scheduling

Question

So this is a bit of a thought provoking question to get across the idea of NP-Completeness by my professor. I get WHY there should be a solution, due to the rules of NP-Completeness, but I don't know how to find it. So here is the problem:

The problem is a simple task scheduling problem with two processors. Each processor can handle one of the n tasks, and any two tasks can be done simultaneously. Each task has an end time e, it must be completed by this time. Each task also has a duration d. All time values, such as end time, duration, and the current time in the system (the time will start at 0), are all integers. So we are given a list of n tasks and we need to use these two processors to schedule them ALL. If any one can not be scheduled, the algorithm has to return no solution. Keep in mind that the order does not matter and it doesn't matter which processor gets which task, as long as there is no overlap and each task finishes before its deadline.

So here is where the problem gets conceptual/abstract, say we have access to a special little function, we have no idea how it works, all we know is this: given a list of n tasks and the current schedule, it will return true or false based on whether or not the algorithm is solvable from this point. This function assumes that the already scheduled tasks are set in stone, and it will only change the times of the unscheduled tasks. However, all this function does is return true or false, it will not give you the proper schedule if it does find a solution. The point is that you can use the special function in the implementation of the scheduling problem. The goal is to solve the scheduling problem, and return a working schedule with every job scheduled properly, using a polynomial number of calls to the special function.

EDIT: To clarify, the question is this: Create a solution to schedule all n tasks without any going over deadline, using a polynomial number of calls to the "special function."

I think this problem is to show that verifying a solution is polynomial, but finding it is nonpolynomial. But my professor is insistent that there is a way to solve this using a polynomial number of calls to the special function. Since the problem as a whole is NP-Complete, this would prove that the nonpolynomial aspect of the runtime comes in during the "decision portion of the algorithm.

If you would like me to clear up anything just leave a comment, I know this wasn't a perfect explanation of the problem.

Answer 1

Given an oracle M that returns true or false only:

input: tasks - list of tasks output: schedule: a triplet(task,processor,start) for each task algorithm:

While there is some unscheduled task:
   let p be the processor that currently finished up his scheduled tasks first
   let x be the first available time on x
   for each unscheduled task t:
      assign t with the triplet: (t,p,x)
      run M on current tasks
      if M answers true:
            break the for loop, continue to next iteration of while loop
      else:
            unassign t, and continue to next iteration of for loop
    if no triplet was assigned, return NO_SOLUTION
return all assigned triplets

• The above runs in polynomial time - it needs O(N^2) calls to M.
• Correctness of the above algorithm can be proved by induction, where the induction hypothesis is After round k of the while loop, if there was a solution before it, there is still a solution after it (and after the assignment of some task). After proving this claim, correctness of the algorithm is achieved trivially for k=#tasks

Formally proving the above claim:

• Base of induction is trivial for k=0.
• Hypothesis: for any k < i, the claim "if there was a solution before round k, there is still one after round k", is correct
• Proof:

Assume there is some solution { (tj,pj,xj) | j=1,...,n}, ordered by j<u <-> xj<xu, and also assume that t1,t2,...,ti-1 is assigned same as the algorithm yielded (induction hypothesis). Now, we are going to assign ti, and we'll be able to do it, since we are going to find the smallest available time stamp (xi), and place some task on it. We are going to find some task, and since ti is a possibility - it will not "fail" and yield "NO_SOLUTION".
Also, since the algorithm does not yields "NO_SOLUTION" in iteration i, from correctness of M, it will yield some task t, that by assigning (t,p,x) - there will still be a solution, and the claim for step i is proven.