NP completeness in task planning

Question

So this is a little thought provoking question to understand the idea of ​​NP-completeness by my professor. I WHY there must be a solution due to NP-completeness rules, but I do not know how to find it. So here is the problem:

The problem is the simple task of scheduling tasks with two processors. Each processor can handle one of the tasks n , and any two tasks can be performed simultaneously. Each task has a finite time e , it should be completed by this time. Each task also has a duration d . All time values, such as end time, duration, and current time in the system (time starts at 0), are integers. So, we are given a list of tasks n , and we need to use these two processors to schedule ALL of them. If someone cannot be scheduled, the algorithm should not return any solution. Keep in mind that order does not matter, and it does not matter which processor receives a task if there is no overlap, and each task ends before the deadline.

So, this is where the problem becomes conceptual / abstract, let's say we have access to a special small function, we have no idea how it works, all we know is this: given the list of tasks n and the current schedule, it will return true or false based on whether the algorithm is allowed from this point. This function assumes that already scheduled tasks are set in stone, and this will only change the time of unplanned tasks. However, this whole function does return true or false; it will not give you the correct schedule if it finds a solution. The fact is that you can use a special function in the implementation of the planning task. The goal is to solve the planning problem and return the work schedule with the proper schedule properly, using the polynomial number of calls to the special function.

EDIT: To clarify, the question arises: create a solution for scheduling all n tasks without any transition to the deadline using the polynomial number of calls for the "special function".

I think this problem is to show that checking the solution is polynomial, but finding it is non-polynomial. But my professor insists that there is a way to solve this using the polynomial number of calls to a special function. Since the problem is NP-Complete in general, this proves that the non-polynomial aspect of runtime arises during the "part of the solution to the algorithm."

If you want me to clarify everything by leaving a comment, I know that this is not an ideal explanation for the problem.

Answer 1

For oracle M , which returns only true or false :

input: tasks - task list output: schedule: 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 works in polynomial time - O(N^2) is required to call O(N^2) .
• The 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 in front of it, a solution remains after it (and after assigning some problem). After proving this statement, the correctness of the algorithm is trivially achieved for k=#tasks

Formally, the proof of the above statement:

• The base of induction is trivial for k = 0.
• Hypothesis: for any k <i, the statement "if there was a solution before round k, then one more after round k", is correct
• Evidence:

Suppose that there exists some solution { (tj,pj,xj) | j=1,...,n} { (tj,pj,xj) | j=1,...,n} , ordered by j<u <-> xj<xu , and also assume that t1, t2, ..., ti-1 is assigned in the same way as the obtained algorithm (induction hypothesis ) Now we assign ti , and we can do this, since we will find the smallest available time xi ( xi ) and put some kind of task on it. We are going to find some kind of task, and since ti is an opportunity - it is not a "failure" and the output is "NO_SOLUTION". In addition, since the algorithm does not give “NO_SOLUTION” in iteration i , from the correctness of M , it will give some problem t , that by assigning (t,p,x) will still be a solution, and the application for step i proved.