因此，这是我的教授提出的一个有点发人深省的问题，以理解NP完全性的概念。我知道为什么应该有一个解决方案，由于NP完全性的规则，但我不知道如何找到它。所以问题是：
该问题是一个具有两个处理器的简单任务调度问题。每个处理器可以处理n任务中的一个，任何两个任务都可以同时完成。每个任务都有一个结束时间e，必须在此时间之前完成。每个任务还具有持续时间d。所有时间值，如结束时间、持续时间和系统中的当前时间(时间将从0开始)，都是整数。因此，我们得到了一个n任务的列表，我们需要使用这两个处理器来调度它们。如果任何一个无法调度，则算法必须不返回任何解决方案。请记住，顺序无关紧要，哪个处理器得到哪个任务也无关紧要，只要没有重叠，并且每个任务都在截止日期前完成。
因此，这就是问题的概念/抽象之处，比如我们可以访问一个特殊的小函数，我们不知道它是如何工作的，我们只知道：给定n任务和当前时间表的列表，它将返回true或false，这取决于算法从这一点上是否可以解决。此功能假定已计划的任务是固定的，并且它只会更改未计划任务的时间。然而，这个函数所做的只是返回true或false，如果它找到了解决方案，它将不会给你正确的时间表。重点是，您可以在实现调度问题时使用特殊函数。目标是解决调度问题，并使用对特殊函数的多项式调用，返回每个作业都已正确调度的工作调度。
编辑：为了澄清，问题是：创建一个解决方案，在不超过截止日期的情况下安排所有n任务，使用对"特殊函数"的多项式调用次数
我认为这个问题是为了证明验证一个解是多项式的，但发现它是非多项式的。但我的教授坚持认为，有一种方法可以通过对特殊函数的多项式调用来解决这个问题。由于整个问题是NP完全的，这将证明运行时的非多项式方面是在算法的"决策部分"中出现的
如果你想让我澄清任何事情，请留下评论，我知道这不是对问题的完美解释。
给定一个仅返回true或false的oracleM：
输入：tasks-任务列表输出：schedule：每个任务的三元组(task、processor、start)算法：
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
- 以上在多项式时间内运行-它需要
O(N^2)对M的调用 - 上述算法的正确性可以通过归纳来证明，其中归纳假设是while循环的
k轮之后，如果在它之前有解，那么在它之后(以及在分配一些任务之后)仍然有解。在证明了这一观点后，对k=#tasks算法的正确性得到了很好的证明
正式证明上述主张：
- 对于k=0，归纳的基是平凡的
- 假设：对于任何k<i、 "如果在k轮之前有一个解，那么在k轮之后仍然有一个"的说法是正确的
- 证明：
假设存在一些由j<u <-> xj<xu排序的解{ (tj,pj,xj) | j=1,...,n}，并且还假设t1，t2，。。。，ti-1的分配与产生的算法相同(归纳假设)。现在，我们将分配ti，我们将能够做到这一点，因为我们将找到最小的可用时间戳(xi)，并在其上放置一些任务。我们将找到一些任务，因为ti是一种可能性-它不会"失败"并产生"NO_SOLUTION"。
此外，由于该算法在迭代i中不产生"NO_SOLUTION"，因此从M的正确性来看，它将产生一些任务t，通过分配(t,p,x)-仍然会有解，并且步骤i的权利要求得到了证明。