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$.