{"entities":{"Q7361065":{"pageid":31518734,"ns":120,"title":"Item:Q7361065","lastrevid":105362558,"modified":"2026-10-07T13:34:22Z","type":"item","id":"Q7361065","labels":{"en":{"language":"en","value":"The Generalized Multiset Ordering is NP-Complete"}},"descriptions":{"en":{"language":"en","value":"AFP entry Multiset_Ordering_NPC"}},"aliases":{},"claims":{"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"e7deb795a08b6b7aa5938712850c4bfb94326dfb","datavalue":{"value":"https://isa-afp.org/entries/Multiset_Ordering_NPC.html","type":"string"},"datatype":"url"},"type":"statement","id":"Q7361065$70D6EEF2-F2C0-4260-AA86-DC51854B5A31","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"c21a91fa45947d63dbf4fb3cbc276ef8f54ca614","datavalue":{"value":{"time":"+2022-04-20T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q7361065$5A163060-344E-4527-9E96-6F56C276F1B0","rank":"normal"}],"P43":[{"mainsnak":{"snaktype":"value","property":"P43","hash":"3e961f1f2b2e533bd88ffdbcd178bd2ef2813f73","datavalue":{"value":"Ren\u00e9 Thiemann","type":"string"},"datatype":"string"},"type":"statement","id":"Q7361065$816B2A54-7E0C-41C2-86FD-F114795F3C7B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P43","hash":"71a18eea766cb0458708e2f59e881d83187048f9","datavalue":{"value":"Lukas Schmidinger","type":"string"},"datatype":"string"},"type":"statement","id":"Q7361065$03F7FDC3-89E6-4C04-86A3-02F38EDBA07E","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"12aea06e863911246695a28bf7a79e0a5b229d14","datavalue":{"value":{"text":"The Generalized Multiset Ordering is NP-Complete","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q7361065$1FB703AD-4F29-495F-9B56-B6937E4C95D7","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"176c734040cecdb169fe87cc5c61798aeb6f149a","datavalue":{"value":"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.","type":"string"},"datatype":"string"},"type":"statement","id":"Q7361065$86CDEDAC-8676-453C-B09E-5245B113FEF2","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"8828146480c327d9a17971b5fa330d92b4921c90","datavalue":{"value":{"entity-type":"item","numeric-id":3429154,"id":"Q3429154"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361065$8D730900-1DBE-4156-A83D-2993273CA21B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d6d3f5f0e6d39b0610560c479018fc71a2adcd20","datavalue":{"value":{"entity-type":"item","numeric-id":1098624,"id":"Q1098624"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361065$BE5A7B67-3DA0-4D81-B518-3AC2CAFC0F1D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bdad75be26f92322fba2c4fc34166d0428ef05f5","datavalue":{"value":{"entity-type":"item","numeric-id":2392415,"id":"Q2392415"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361065$AC1E95D2-C0AF-4F03-BADB-18DF432A6D4C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d8191cf0bfbb217d8b509ce0cb8681f64b916ac1","datavalue":{"value":{"entity-type":"item","numeric-id":5111915,"id":"Q5111915"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361065$FF3EB0CF-82B4-455B-B765-07E475D8B2E5","rank":"normal"}],"P37":[{"mainsnak":{"snaktype":"value","property":"P37","hash":"9a21a8eebe97539644aa32b24dda137c12e751dc","datavalue":{"value":{"entity-type":"item","numeric-id":40327,"id":"Q40327"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361065$7C858841-E49A-46AE-AE04-F33F72F643C9","rank":"normal"}],"P585":[{"mainsnak":{"snaktype":"value","property":"P585","hash":"4818bbf7d89ba2c3179bc556d045d6dc521fe671","datavalue":{"value":{"entity-type":"item","numeric-id":7361813,"id":"Q7361813"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361065$BA3D1520-C3B1-430C-8DE6-2C7CAF8C71D6","rank":"normal"}],"P2651":[{"mainsnak":{"snaktype":"value","property":"P2651","hash":"edf8a8949edec3767dd80b6d3acecc92e5d25f1c","datavalue":{"value":{"entity-type":"item","numeric-id":7360818,"id":"Q7360818"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361065$39D39E5E-E8D7-44A5-9148-ACA7CD2FDA19","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"908c3454b3659c4b140ccce33c5aee31081edc8d","datavalue":{"value":{"entity-type":"item","numeric-id":5976450,"id":"Q5976450"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361065$1FE56DD3-BA30-43F5-88B9-C58EEC5C13C5","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"The Generalized Multiset Ordering is NP-Complete","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/The_Generalized_Multiset_Ordering_is_NP-Complete"}}}}}