System BV is NP-complete

Ozan Kahramanogullari <ozan-jNDFPZUTrfTw9Zu3TmXbXSJk02hg1TJes0AfqQuZ5sE@public.gmane.org>
Newsgroups gmane.science.mathematics.frogs
Message-ID <Pine.GSO.4.61.0502121715010.13918@gkws0.informatik.uni-leipzig.de>
Dear All,

The paper given as a link below is the draft of the paper 
on the np-completeness of system BV. I'll be glad to have
your comments or suggestions.

Regards,
-Ozan

http://www.informatik.uni-leipzig.de/~ozan/Papers/npc.pdf

System BV is NP-complete

Abstract:
---------
System $\BV$ is an extension of multiplicative linear
logic (extended by the rules mix and nullary mix)
by a self-dual, noncommutative connective. In this paper,
I show that system $\BV$ is NP-complete. I show the
NP-hardness by encoding the 3-Partition problem into $\FBV$,
which is the extension of multiplicative linear logic
with the rules  mix and nullary mix. This way, I also
show that multiplicative linear logic extended with the
rules mix and nullary mix is  NP-complete, since system
$\BV$ is a conservative extension of system $\FBV$.
lmpx.com only provides a reader for public news (NNTP) servers. It is not affiliated with the servers or forums shown here and is not responsible for the content of articles, which is written by their respective authors.