Uniprocessor Feasibility of Sporadic Tasks Remains coNP-Complete under Bounded Utilization
Uniprocessor Feasibility of Sporadic Tasks Remains coNP-Complete under Bounded Utilization
复制标题
在有限利用率下，单处理器处理零星任务的可行性仍然是 coNP-Complete
DOI：
--
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
W. Yi
中科院分区：
文献类型：
--
作者：
Pontus Ekberg;W. Yi
实时调度理论中的一个核心问题是判定一个具有约束截止期的偶发任务系统在抢占式单处理机上是否可行。众所周知，这个问题在一般情况下是强coNP完全的，但对于利用率由任何常数c从上面限定的实例，也存在伪多项式时间解，其中0 <; c <; 1。长期以来，人们一直不知道有界情况是否也有多项式时间解。我们证明了对于任何常数c的选择，使得0 <; c <; 1，有界可行性问题是（弱）coNP-完全的，因此不存在多项式时间解，除非P = NP。
A central problem in real-time scheduling theory is to decide whether a sporadic task system with constrained deadlines is feasible on a preemptive uniprocessor. It is known that this problem is strongly coNP-complete in the general case, but also that there exists a pseudo-polynomial time solution for instances with utilization bounded from above by any constant c, where 0 <; c <; 1. For a long time it has been unknown whether the bounded case also has a polynomial-time solution. We show that for any choice of the constant c, such that 0 <; c <; 1, the bounded feasibility problem is (weakly) coNP-complete, and thus that no polynomial-time solution exists for it, unless P = NP.