{"entities":{"Q1106217":{"pageid":1116966,"ns":120,"title":"Item:Q1106217","lastrevid":67012005,"modified":"2026-04-12T14:19:11Z","type":"item","id":"Q1106217","labels":{"en":{"language":"en","value":"Inclusion relationships among permutation problems"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4061245"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1106217$EDD8486D-8009-4452-BE81-5D0EB798EF8E","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"20a2cdf43cc46c0a2ae5712f3c04353fe37c03de","datavalue":{"value":{"text":"Inclusion relationships among permutation problems","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1106217$BCDA0D20-F9B1-4A23-A7CD-368E87F15C0B","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"8a4ac285901ad0a9b394565b254db871846e6d0a","datavalue":{"value":"0651.05007","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1106217$ECA0F5CB-E409-4594-9118-1E69D57789D2","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"37c5c96f663ec80bebf6bf621548ae1862d0f133","datavalue":{"value":"10.1016/S0166-218X(87)90078-3","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1106217$8E638ECD-2493-4550-BA2C-3324E3BEC7EF","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"2cfe6cd4b6f96e92f55b16a55e8d306d4caaa140","datavalue":{"value":{"entity-type":"item","numeric-id":1106216,"id":"Q1106216"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1106217$594F10AA-1423-48B4-A3F8-53F44C59C795","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"7059dc37480e3ec45454f04d5e0c8b67678d4a4d","datavalue":{"value":{"entity-type":"item","numeric-id":293219,"id":"Q293219"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1106217$EF133735-CC59-4A18-BDBA-59048F7EF70A","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"087f55844cc920aae060b09644168bf17b022e1a","datavalue":{"value":{"entity-type":"item","numeric-id":96294,"id":"Q96294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1106217$EC7388DC-9A87-4786-8C27-B172268A173B","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5ae48c61eed19d1e1e1f33f9255d5b329362d064","datavalue":{"value":{"time":"+1987-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1106217$DF1FBEF0-5043-4B13-8D95-5DB34AEB2173","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"51a5f7930ad7e9a13b0f31137361626a856b6732","datavalue":{"value":"Let \\(X=\\{x_ 1,...,x_ n\\}\\) be a set of n elements. A permutation problem on X is a decision problem in NP which consists of determining whether there exists an n element permutation satisfying a set of ordering constraints expressed as collections of permutations of at most k elements of X. Several well-known NP-complete problems such as cyclic ordering, betweenness, and serializability can be expressed as permutation problems.    If we consider symbol preserving polynomial reductions, i.e., reductions that do not make use of additional elements, strict inclusion relationships among permutation problems can be proved. In particular, the serializability problem is shown to be included in the deadlock avoidance one.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1106217$13710A99-027C-4651-B2DE-D88CDFAE8745","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6247f04fad65d359a20e559b3e9499d6219d492e","datavalue":{"value":"05A05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1106217$8FF690D2-F57D-4CC3-8FE5-A9DFC8A47DA7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d033eacd9a9c3d598bf2694ab5bd270d31928a0c","datavalue":{"value":"62C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1106217$2366748E-94D5-4168-AF35-2E2A9306AB4D","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"7955195b6cc333472783b21e1cae681d157a3dda","datavalue":{"value":"4061245","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1106217$7B543990-74D5-4977-8F3B-380B0FF2966E","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7b75e98f5ef25f66ae94d651300ae18d732eb818","datavalue":{"value":"permutation problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1106217$2BC6688B-E84F-4117-B7D5-525FD2DC5B89","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5ab14670fd645ceec284d741b18aecb5f5131180","datavalue":{"value":"decision problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1106217$F85CA703-D3E7-4B70-9FDF-1EF17E6A108E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1c8c9e80036612c21ad2ec3b6579e3228fd2ea1e","datavalue":{"value":"NP-complete problems","type":"string"},"datatype":"string"},"type":"statement","id":"Q1106217$66E170CB-DB65-476A-B21B-68FD75F5635A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b335e00a897da3b38f4522ee33d5fc0ca0408fc1","datavalue":{"value":"inclusion relationships","type":"string"},"datatype":"string"},"type":"statement","id":"Q1106217$10B89A5B-7F22-4C7A-AEFC-82FE8F19F167","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"15c6902e78fdcb946ed1d44382f0f09d0e6b09af","datavalue":{"value":"serializability","type":"string"},"datatype":"string"},"type":"statement","id":"Q1106217$401D9B40-AEAC-4104-897A-B8E2F721E3D0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"08c70abc74354f81e14c1950aab27c1fd80288d6","datavalue":{"value":"deadlock avoidance","type":"string"},"datatype":"string"},"type":"statement","id":"Q1106217$FD64C9CB-1738-4169-9E6A-C48E56D6D497","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1106217$2CC27E4B-5632-4B00-99E9-B0B775E15D26","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3f26b76ebdbff1b7b4f90738d45f90682d5bff2d","datavalue":{"value":{"entity-type":"item","numeric-id":1248373,"id":"Q1248373"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f27ee0c7189f227afdcda8da78ae465d4a60780c","datavalue":{"value":{"amount":"+0.7102802395820618","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1106217$596A4A3E-887B-43EE-8513-1793955CBE1E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fd3738dab27ce30f4a9c27fbf619d37e4dcbe69f","datavalue":{"value":{"entity-type":"item","numeric-id":2722006,"id":"Q2722006"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0acc47a0ef9bd2b51d4f061f9d5ee01231990fdb","datavalue":{"value":{"amount":"+0.7102487683296204","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1106217$F4B8CA7A-025B-4824-8879-1F1CBE78E73C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9e2ce5cd085b9767c537f736f568f17ee33d2d1c","datavalue":{"value":{"entity-type":"item","numeric-id":1088647,"id":"Q1088647"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0acc47a0ef9bd2b51d4f061f9d5ee01231990fdb","datavalue":{"value":{"amount":"+0.7102487683296204","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1106217$D1476E68-F5EE-477F-9866-0D5CAFA81D0C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"63fb05c3830fe1594c4becb751687e98d8e0a279","datavalue":{"value":{"entity-type":"item","numeric-id":3682404,"id":"Q3682404"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"53d73e20eb0a23386aed6fc7636af7c1ec9d1e32","datavalue":{"value":{"amount":"+0.7016667127609253","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1106217$556AC2B3-FACC-4879-8752-0045C0E75242","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4e6ef8aa847e42b7458d7e59b4635190c2f7a5fa","datavalue":{"value":{"entity-type":"item","numeric-id":392031,"id":"Q392031"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"add479e6ab1ac0f2cae5261a26a146e622408809","datavalue":{"value":{"amount":"+0.7016457319259644","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1106217$84996C82-5E89-489C-9250-1772A09A900B","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Inclusion relationships among permutation problems","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Inclusion_relationships_among_permutation_problems"}}}}}