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

DOI10.1007/978-3-319-90686-7_2MaRDI QIDQ1648864OpenAlexFDO

Authors Satoshi Matsuoka

Publication date 9 July 2018

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

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)

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

Cited in

(4)

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

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)