On the complexity of the partner units decision problem

摘要

The partner units problem is an acknowledged hard benchmark problem for the logic programming community with various industrial application fields like CCTV surveillance or railway safety systems. Whereas many complexity results exist for the optimization version of the problem, complexity for the decision variant, which from a practical point of view is more important, is widely unknown. In this article we show that the partner units decision problem is NP-complete in general and also for various subproblems of industrial importance.