|
System BV is NP-complete: msg#00006science.mathematics.frogs
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$. |
|
| <Prev in Thread] | Current Thread | [Next in Thread> |
|---|---|---|
| Previous by Date: | Re:Calculus of structures and sequent calculus: 00006, Alessio Guglielmi |
|---|---|
| Next by Date: | Olive oil: 00006, Alessio Guglielmi |
| Previous by Thread: | A local system for intuitionistic logici: 00006, Alwen Tiu |
| Next by Thread: | Workshop: 00006, Alessio Guglielmi |
| Indexes: | [Date] [Thread] [Top] [All Lists] |
| News | FAQ | advertise |