System BV is NP-complete | Zendy

Ozan Kahramanoğulları | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

System BV is NP-complete

Author(s) -

Ozan Kahramanoğulları

Publication year - 2005

Publication title -

electronic notes in theoretical computer science

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 0.242

H-Index - 60

ISSN - 1571-0661

DOI - 10.1016/j.entcs.2005.05.026

Subject(s) - conservative extension , concurrency , extension (predicate logic) , linear logic , computer science , operator (biology) , logical connective , mathematics , proof theory , completeness (order theory) , dual (grammatical number) , commutative property , multiplicative function , algorithm , theoretical computer science , algebra over a field , discrete mathematics , programming language , pure mathematics , art , mathematical analysis , biochemistry , chemistry , geometry , literature , repressor , transcription factor , mathematical proof , gene

ystem BV is an extension of multiplicative linear logic (MLL) with the rules mix, nullary mix, and a self-dual, non-commutative logical operator, called seq. While the rules mix and nullary mix extend the deductive system, the operator seq extends the language of MLL. Due to the operator seq, system BV extends the applications of MLL to those where sequential composition is crucial, e.g., concurrency theory. System FBV is an extension of MLL with the rules mix and nullary mix. In this paper, by relying on the fact that system BV is a conservative extension of system FBV, I show that system BV is NP-complete by encoding the 3-Partition problem in FBV. I provid a simple completeness proof of this encoding by resorting to a novel proof theoretical method for reducing the nondeterminism in proof search, which is also of independent interest

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research