This paper aims at being a step in the precise classification of the many NP-complete problems which belong to NLIN (non-deterministic linear time complexity on random-access machines), but are seemingly not NLIN-complete. We define the complexity class LIN-LOCAL ― the class of problems linearly reducible to problems defined by Boolean local constraints ― as well as its planar restriction LIN-PLAN-LOCAL. We show that both "local" classes are rather computationally robust and that SAT and PLAN-SAT are complete in classes LIN-LOCAL and LIN-PLAN-LOCAL, respectively. We prove that some unexpected problems that involve some seemingly global constraints are complete for those classes. E.g., VERTEX-COVER and many similar problems involving cardinality constraints are LIN-LOCAL-complete. Our most striking result is that PLAN-HAMILTON ― the planar version of the Hamiltonian problem ― is LIN-PLAN-LOCAL and even is LIN-PLAN-LOCAL-complete. Further, since our linear-time reductions also turn out to be parsimonious, they yield new DP-completeness results for UNIQUE-PLAN-HAMILTON and UNIQUE-PLAN-VERTEX-COVER.
展开▼
