logo       

System BV is NP-complete: msg#00006

science.mathematics.frogs

Subject: System BV is NP-complete

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>
Google Custom Search

News | FAQ | advertise