| Home |
| About |
| Submission |
| Updating Entries |
| Using Entries |
| Search |
| Statistics |
| Index |
| Download |
The Generalized Multiset Ordering is NP-Complete
| Title: | The Generalized Multiset Ordering is NP-Complete |
| Authors: | René Thiemann (rene /dot/ thiemann /at/ uibk /dot/ ac /dot/ at) and Lukas Schmidinger |
| Submission date: | 2022-04-20 |
| 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. |
| BibTeX: |
@article{Multiset_Ordering_NPC-AFP,
author = {René Thiemann and Lukas Schmidinger},
title = {The Generalized Multiset Ordering is NP-Complete},
journal = {Archive of Formal Proofs},
month = apr,
year = 2022,
note = {\url{https://isa-afp.org/entries/Multiset_Ordering_NPC.html},
Formal proof development},
ISSN = {2150-914x},
}
|
| License: | BSD License |
| Depends on: | Weighted_Path_Order |
|
Proof outline Proof document |
| Browse theories |
| Download this entry |
| Older releases: None |