Email Gateway (Apr 22 2022 at 09:32): Email Gateway (Apr 22 2022 at 09:32):From: Tobias Nipkow <nipkow@in.tum.de>
The Generalized Multiset Ordering is NP-Complete
René Thiemann and Lukas Schmidinger
We consider the problem of comparing two multisets via the generalized multiset
ordering. We show that the corresponding decision problem is NP-complete. To be
more precise, we encode multiset-comparisons into propositional formulas or into
conjunctive normal forms of quadratic size; we further prove that satisfiability
of conjunctive normal forms can be encoded as multiset-comparison problems of
linear size. As a corollary, we also show that the problem of deciding whether
two terms are related by a recursive path order is NP-hard, provided the
recursive path order is based on the generalized multiset ordering.
https://www.isa-afp.org/entries/Multiset_Ordering_NPC.html
Enjoy!
smime.p7s
Last updated: Jul 15 2022 at 23:21 UTC