A Fully Abstract Relational Model of Syntactic Control of Interference

McCusker, Guy (2002) A Fully Abstract Relational Model of Syntactic Control of Interference. In: Computer Science Logic, Edinburgh, Scotland.

Full text not available from this repository.

Abstract

In an effort to investigate some linear analogue of the conjecture P $\neq$ NP, that is DLIN $\neq$ NLIN (deterministic/nondeterministic linear time complexity on random-access machines), this paper aims at being a step in the precise classification of the many NP-complete problems
which are seemingly not NLIN-complete. We define and discuss 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 computationally robust and give some arguments for the conjecture that the following "linear hierarchy" is strict at each level: DLIN $\subseteq$ LIN-PLAN-LOCAL $\subseteq$ LIN-LOCAL $\subseteq$ NLIN. After showing 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 indeed belong to those classes and are complete for them. More precisely, we show that VERTEX-COVER and many similar problems involving cardinality constraints are LIN-LOCAL-complete. Our most striking and most technical result is that PLAN-HAMILTON -- the planar version of the Hamiltonian problem, a problem that involves a connectivity constraint of solutions -- 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.

Item Type: Conference or Workshop Item (Paper)
Schools and Departments: School of Engineering and Informatics > Informatics
Depositing User: EPrints Services
Date Deposited: 06 Feb 2012 19:45
Last Modified: 07 Jun 2012 11:54
URI: http://sro.sussex.ac.uk/id/eprint/22035
📧 Request an update