摘要
旋转调度是一个基本的调度问题，其中每个任务 $i$ 关联一个正整数 $d_i$，目标是在每个时间槽中调度一个任务，确保每个任务在每 $d_i$ 个时间槽中至少出现一次。尽管被猜测为 PSPACE 完全，但尚未确定旋转调度是否 NP-hard（除非使用紧凑的输入编码）或甚至包含在 NP 中。
我们引入了 k-访问，这是旋转调度的有限版本，给定 $n$ 个截止时间，目标是每个任务恰好调度 $k$ 次。虽然我们观察到 1-访问问题是微不足道的，但我们证明 2-访问是强 NP 完全的，这通过从数值三维匹配（N3DM）进行的惊人归约得以实现。在归约的中间步骤中，我们定义了 N3DM 的 NP 完全变体，这可能具有独立的兴趣。
我们进一步将强 NP 难度的结果扩展到 $k$ 访问 $k \geq 2$ 的广义版本，其中每个任务的截止时间可以在调度中变化，以及旋转调度的类似广义版本，从而为确定旋转调度的复杂性取得进展。此外，我们证明，如果所有截止时间都是不同的，则 2-访问可以在线性时间内解决，这使其成为少数自然问题之一，展现出输入为集合时在 P 中而输入为多重集时为 NP 完全的有趣二分。
我们通过从 2-访问到一种我们称之为位置匹配的 N3DM 变体的图灵归约实现了这一点。此外，我们还展示了一种针对与输入截止时间彼此接近的值相关的参数化的 2-访问 FPT 算法，以及一种针对最多有两个不同截止时间的实例的线性时间算法。
博主点评： 本文通过对旋转调度问题进行深入探讨，揭示了其复杂性级别，特别是 k-访问问题的 NP 完全性，为后续研究奠定了基础。作者的归约方法和算法设计展示了调度问题的多样性及其在理论计算机科学中的重要性。值得注意的是，针对特殊情况的线性时间算法提供了实用的解决方案，为实际应用提供了理论支持。