University of Sussex
Browse

File(s) not publicly available

A Fully Abstract Relational Model of Syntactic Control of Interference

presentation
posted on 2023-06-07, 23:55 authored by Guy McCusker
In an effort to investigate some linear analogue of the conjecture P $
eq$ NP, that is DLIN $
eq$ 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.

History

Publication status

  • Published

Publisher

Springer-Verlag

Volume

Lectur

Pages

15.0

Presentation Type

  • paper

Event name

Computer Science Logic

Event location

Edinburgh, Scotland

Event type

conference

ISBN

3-540-44240-5

Department affiliated with

  • Informatics Publications

Full text available

  • No

Peer reviewed?

  • Yes

Legacy Posted Date

2012-02-06

Usage metrics

    University of Sussex (Publications)

    Categories

    No categories selected

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC