期刊
THEORY OF COMPUTING SYSTEMS
卷 53, 期 4, 页码 569-582出版社
SPRINGER
DOI: 10.1007/s00224-013-9445-4
关键词
Planning and scheduling; Computational complexity; Polynomial hierarchy
资金
- Netherlands Organisation for Scientific Research (NWO) [639.033.403]
- DIAMANT (an NWO mathematics cluster)
- Alexander von Humboldt Foundation, Bonn, Germany
We study a motion planning problem where items have to be transported from the top room of a tower to the bottom of the tower, while simultaneously other items have to be transported in the opposite direction. Item sets are moved in two baskets hanging on a rope and pulley. To guarantee stability of the system, the weight difference between the contents of the two baskets must always stay below a given threshold. We prove that it is -complete to decide whether some given initial situation of the underlying discrete system can lead to a given goal situation. Furthermore we identify several polynomially solvable special cases of this reachability problem, and we also settle the computational complexity of a number of related questions.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据