Direct Encodings of NP-Complete Problems into Horn Sequents of Multiplicative Linear Logic

Satoshi Matsuoka

Direct Encodings of NP-Complete Problems into Horn Sequents of Multiplicative Linear Logic

2018

Satoshi Matsuoka

In this paper, we provide direct encodings into Horn sequents of Multiplicative Linear Logic for two NP-complete problems, 3D MATCHING and PARTITION. Their correctness proofs are given by using a characterization of multiplicative proof nets.

Keywords:

Computer science
Discrete mathematics
Algorithm
Mathematical proof
Correctness
NP-complete
Multiplicative function
Partition (number theory)
3-dimensional matching
Linear logic
Theoretical computer science
correctness proofs
Algebra

Correction
Source
Cite
Save
Machine Reading By IdeaReader

References

Citations