Direct encodings of NP-complete problems into Horn sequents of multiplicative linear logic

DOI10.1007/978-3-319-90686-7_2OpenAlexW2802667626MaRDI QIDQ1648864FDOQ1648864

Authors: Satoshi Matsuoka 

Publication date: 9 July 2018

Full work available at URL: https://doi.org/10.1007/978-3-319-90686-7_2

Recommendations

• Constant-only multiplicative linear logic is NP-complete
• The complexity of Horn fragments of linear logic
• scientific article; zbMATH DE number 1615234
• Decision problems for propositional linear logic
• Lambek calculus is NP-complete

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Proof-theoretic aspects of linear logic and other substructural logics (03F52)

Cited In (4)

• System BV is NP-complete
• On Hardness of Multilinearization and VNP-Completeness in Characteristic 2
• Constant-only multiplicative linear logic is NP-complete
• A formal model for a linear time correctness condition of proof nets of multiplicative linear logic

This page was built for publication: Direct encodings of NP-complete problems into Horn sequents of multiplicative linear logic

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1648864)