{"entities":{"Q922700":{"pageid":924548,"ns":120,"title":"Item:Q922700","lastrevid":65405190,"modified":"2026-04-12T02:22:47Z","type":"item","id":"Q922700","labels":{"en":{"language":"en","value":"Maximum bounded 3-dimensional matching is MAX SNP-complete"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4170090"}},"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":"Q922700$C5A0223E-8721-4705-8B56-5290898F37E9","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"ad587644ecbf254e98d6a14eec3853e48fd4919f","datavalue":{"value":{"text":"Maximum bounded 3-dimensional matching is MAX SNP-complete","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q922700$16E3457B-674E-4D07-9117-8CB8C5D297FE","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"3788aff2889ebf8a56319a69aea6cc8ed328422b","datavalue":{"value":"0711.68045","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q922700$6938EE43-4C62-4453-A90A-9145B5B65CA8","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"c902904def30bc9433a1468c99c06b6175155f0e","datavalue":{"value":"10.1016/0020-0190(91)90246-E","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q922700$8DC8E041-7C00-4705-B564-EB4F2A4286FB","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"3c40085a5a3aabaacd15d3477a46b09467a0d262","datavalue":{"value":{"entity-type":"item","numeric-id":293217,"id":"Q293217"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q922700$5271F4DF-B25A-400C-9B97-BC99971C0EB6","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"52fa7d44b58d0511cb8993765bd916aef86052d8","datavalue":{"value":{"entity-type":"item","numeric-id":63092,"id":"Q63092"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q922700$2CCE23D1-46FE-44E1-92D0-11611097E858","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"391107ffc7a24346d69c573e292e4ff4587e3aaa","datavalue":{"value":{"time":"+1991-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":"Q922700$62C1BADA-5DB6-45BF-8952-33EC33428FED","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b4346faa01bb5fb0576370374d6456afd58d5666","datavalue":{"value":"68Q15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q922700$407BDA7C-7C93-4E47-8BA3-BA46C8F1B286","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"35cb8465ca85ba26995d54be2905dc35556d665c","datavalue":{"value":"90C27","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q922700$1DC475B2-4EB1-4A39-9281-EF912FC7BB32","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d7656d1c841701431b0b3d99d23720089a267cbb","datavalue":{"value":"03D15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q922700$2475AF9F-D962-4F70-A74F-5464D50A5636","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"304b3989fd9419fce857a5c78d0464d547bcb329","datavalue":{"value":"4170090","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q922700$DCB67D3B-258B-457E-A8A8-F17511C45895","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"dc058f54aac0023b7543c366366b86bc4e72c56b","datavalue":{"value":"approximation","type":"string"},"datatype":"string"},"type":"statement","id":"Q922700$89E32D2E-991A-4ABA-AFEF-00D7BAA275A5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b93d69ebc1c51cfee06b00c8b748e2b4275c0266","datavalue":{"value":"combinatorial problems","type":"string"},"datatype":"string"},"type":"statement","id":"Q922700$1FD4072F-4BC9-4642-B932-A5A1F8C591C0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2ba0cc3f7aaac8445724ef309c9eecb57f5a563d","datavalue":{"value":"computational complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q922700$3A0879F5-D7FE-4403-A9D7-AA36EC0F379C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"62a37eab95d4826773244b163301805461bad199","datavalue":{"value":"MAX SNP- complete problems","type":"string"},"datatype":"string"},"type":"statement","id":"Q922700$F1EADE89-EC93-4B11-A2C6-FACBEA3F6C91","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"2cdbe095567c08052ef6c7933167d897acabb2b6","datavalue":{"value":"Q57255181","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q922700$DCB62674-BF29-495B-8118-25635E464273","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":"Q922700$7DE9660E-6F0E-4635-A902-FD78C739FE07","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"fff3d0b01d7ce8178154b0d471662887ae6a912d","datavalue":{"value":{"entity-type":"item","numeric-id":5096160,"id":"Q5096160"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q922700$6D1F7B3D-544D-4A30-9DCE-0F97D2A6E67B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1207e6aa1fc06e1913a02d7555e24510b78299db","datavalue":{"value":{"entity-type":"item","numeric-id":4744064,"id":"Q4744064"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q922700$2099BC87-C344-4E28-879D-1A497C734599","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"836ad2a04f82225da478ca9f694f5cd99360b315","datavalue":{"value":{"entity-type":"item","numeric-id":4198056,"id":"Q4198056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q922700$29272569-C97B-4E01-977B-CDB92082832E","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"193521e1c0174395267561401c23ece9ab1e555b","datavalue":{"value":"https://doi.org/10.1016/0020-0190(91)90246-e","type":"string"},"datatype":"url"},"type":"statement","id":"Q922700$7F5670DA-6574-4C84-A6E3-B82D8AE153EB","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"51fbd9fef009ef4ed6415cc945968bb6ee7d534c","datavalue":{"value":"W2071016718","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q922700$D09E8109-A493-4AEC-B2BE-05AB0B48879B","rank":"normal"}],"P1635":[{"mainsnak":{"snaktype":"value","property":"P1635","hash":"f08dbdda9b8c0b9061df9f01e3ca289192f50002","datavalue":{"value":"journals/ipl/Kann91","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q922700$F650F664-B6E1-443B-A63C-D520A94D391F","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"266ae6968737ee1b0270f5ecb112581ed5f8be96","datavalue":{"value":{"entity-type":"item","numeric-id":1321820,"id":"Q1321820"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dd5426dc625196985bf8b2233f5808f9e3bda7db","datavalue":{"value":{"amount":"+0.9182398","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q922700$ABC050EA-8FF8-4C94-A965-E35AD841E46D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d28575795900eb9ecce5d2f548eb8fc3c178ba4a","datavalue":{"value":{"entity-type":"item","numeric-id":1626726,"id":"Q1626726"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3acbed7a63ba575e435ec9d716f98658adf255e0","datavalue":{"value":{"amount":"+0.8146555","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q922700$9179011D-074F-4656-BD13-AABC1B07B4B3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e01637b2fcd1af0df20247760c4bed52030c34f1","datavalue":{"value":{"entity-type":"item","numeric-id":1877645,"id":"Q1877645"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c78fdba860c5a90a84ae86cb1a2a4f337ced90dc","datavalue":{"value":{"amount":"+0.8110938","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q922700$2E6C302D-8927-4094-926B-F2FBFB8AC8F4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7880c54fad19ab406d7a2092d7d18ec8ef22f4c1","datavalue":{"value":{"entity-type":"item","numeric-id":4474098,"id":"Q4474098"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c78fdba860c5a90a84ae86cb1a2a4f337ced90dc","datavalue":{"value":{"amount":"+0.8110938","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q922700$D3014F46-7881-4096-8CC4-C097BB0E87B0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"141cde2f415f2e8606a648ea650ba7fc457ec481","datavalue":{"value":{"entity-type":"item","numeric-id":1014835,"id":"Q1014835"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a84a634399a2f7fad8c6ca9054b47c7af67d2b68","datavalue":{"value":{"amount":"+0.8089033","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q922700$E78ECDFF-0979-4EE9-9AB4-B80036DDC4D3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0f8d58bf39669ae26c7dee1cb2b9bf7d2d169ee9","datavalue":{"value":{"entity-type":"item","numeric-id":3348423,"id":"Q3348423"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3b290c819f8c2b6c0592799eb4add2e0f36842fb","datavalue":{"value":{"amount":"+0.8052131","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q922700$E242BAAF-7C81-4D7E-A745-6399BD5791E3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"808356180f914491f1f77ef3cd143ada28eeeace","datavalue":{"value":{"entity-type":"item","numeric-id":1043589,"id":"Q1043589"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9d4aaec8ea63979bfb74b8d51684e663c131cd5c","datavalue":{"value":{"amount":"+0.8004068","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q922700$6EC0BA03-3F74-4E27-8960-C38D9D7F18E0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2edef8ae2741893c1a13beb85852d1f0f80038fd","datavalue":{"value":{"entity-type":"item","numeric-id":3499722,"id":"Q3499722"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a1c21315a40f7363101113fd92bdfe2a41848374","datavalue":{"value":{"amount":"+0.796345","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q922700$7D583455-8FF9-421A-BC97-E068A9D1EA0B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6c45546ed8551786ffd1e85803e0e1ceac1a3647","datavalue":{"value":{"entity-type":"item","numeric-id":4729838,"id":"Q4729838"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"aa9dfeae65bc7b0eddb08e30df08f2bc7081b7e8","datavalue":{"value":{"amount":"+0.7962979","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q922700$0730E063-99CA-48F6-9D00-D6915E3537A7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"af452835e81fdfb65ffbce651490bc0f60227fba","datavalue":{"value":{"entity-type":"item","numeric-id":4953913,"id":"Q4953913"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"029f8c31aecf6ae1a321773ed71b99cee9e6b3fa","datavalue":{"value":{"amount":"+0.7933055","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q922700$419329D6-B6F1-4E56-9AAC-764D1E7BDBAD","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Maximum bounded 3-dimensional matching is MAX SNP-complete","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Maximum_bounded_3-dimensional_matching_is_MAX_SNP-complete"}}}}}