The Generalized Multiset Ordering Is NP-Complete

RenĂ© Thiemann đŸ“§ and Lukas Schmidinger

April 20, 2022

Abstract

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.
BSD License

Topics

Theories of Multiset_Ordering_NPC