{"entities":{"Q716333":{"pageid":718182,"ns":120,"title":"Item:Q716333","lastrevid":63780996,"modified":"2026-04-11T15:30:07Z","type":"item","id":"Q716333","labels":{"en":{"language":"en","value":"Complexity classes of equivalence problems revisited"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5882208"}},"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":"Q716333$4214FBB1-3AF8-42FF-9FD2-C4CDC8D14F67","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"59e324b581652a1ece0259a621367a49885af22e","datavalue":{"value":{"text":"Complexity classes of equivalence problems revisited","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q716333$4CAC5C9B-C7B9-4CEE-AF4A-5AE236FF8506","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"2789979e16ffa096522e93760ced6498359a1aff","datavalue":{"value":"1238.68061","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q716333$DACD0981-826F-48AD-98D1-FE247892990A","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"855e30996183ae5970f026fb05ae3c2a5bb0c9a7","datavalue":{"value":{"entity-type":"item","numeric-id":716332,"id":"Q716332"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q716333$08539244-6458-41F2-8B03-17F81915A2B1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"76fe4057f7ea6f8b50335cff0c4e37872da7faa9","datavalue":{"value":{"entity-type":"item","numeric-id":1318472,"id":"Q1318472"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q716333$207D09D1-D469-47CA-A3DB-1BD7C56B40A6","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"fa2d1ad91af9619c8dd37ab889fe279a84c4057e","datavalue":{"value":{"entity-type":"item","numeric-id":259032,"id":"Q259032"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q716333$F73EC8E1-4E71-43DD-9BC9-0ED8CA792E03","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"2b6451ced8faca5a776070094e00eadb4afa93f8","datavalue":{"value":{"time":"+2011-04-28T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q716333$669A99B7-19B8-4D77-801A-76BA78084AB2","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"f6406e8154fc307325368c30948e3e2d540562c6","datavalue":{"value":"Equivalence relations on words over a finite alphabet give rise to a number of natural computational problems; in particular, the recognition problem (decide equivalence), the invariant problem (find a function whose kernel relation is the given equivalence relation), the canonical form problem (find a function that selects an element in each equivalence class) and the first canonical form problem (determine the least element in each class according to some natural order such as length-lex). The current work extends the results of \\textit{A. Blass} and \\textit{Yu. Gurevich} [SIAM J. Comput. 13, 682--689 (1984; Zbl 0545.68035)] and introduces connections to probabilistic and quantum computation.  Among other results, it is shown in particular that if every relation with a polynomial time solvable recognition problem already admits a polynomial time solution to the invariant problem, then UP is contained in BQP. Various oracles are constructed that demonstrate potential separation between the different problems. For example, there is an oracle for which not every polynomial time decidable recognition problem admits a polynomial time invariant, nor does the invariant admits a polynomial time solution to the canonical form problem.","type":"string"},"datatype":"string"},"type":"statement","id":"Q716333$7812B6C2-4121-47D6-AF94-91E01263BF43","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"8564e78441affe432e0619719bb2eec6830d68d9","datavalue":{"value":{"entity-type":"item","numeric-id":616505,"id":"Q616505"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q716333$AD8D531A-9327-47A1-87DA-F96A981B06D2","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b4346faa01bb5fb0576370374d6456afd58d5666","datavalue":{"value":"68Q15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q716333$CB58D9BF-5FCC-47DA-BD2F-B45C70736CEF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"7af17f227fda8daecc6b4cd26e5d774fa965085f","datavalue":{"value":"81P68","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q716333$DCFBDC39-4E79-4900-AF05-214252517FF3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"35bbdcbda53152c249a7f99650e19b5ef62999f2","datavalue":{"value":"68Q10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q716333$FB8DB357-CFE3-4608-831B-64045C92FA53","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q716333$7109D765-067A-4F97-834C-E7270AAED2A8","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"a3b06f4ef2c11bced790653ca36539bab2d626d4","datavalue":{"value":"5882208","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q716333$D3CBCACE-05F9-4DA4-AB55-F44BF25C28CE","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2ba0cc3f7aaac8445724ef309c9eecb57f5a563d","datavalue":{"value":"computational complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q716333$F55E7C53-FB26-4746-959E-31D8F4BE041F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cd7884f20c8f87422bbc52076fab6a08675c0a24","datavalue":{"value":"equivalence relation","type":"string"},"datatype":"string"},"type":"statement","id":"Q716333$762AD631-BCE7-4C0C-BD70-D1C349993A3E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2f5f9fa7c99fed84610c34025a6959701496fde6","datavalue":{"value":"normal form","type":"string"},"datatype":"string"},"type":"statement","id":"Q716333$470D754F-B370-4A55-A820-959BEF8E24D7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b181606adcba6432b0019d481c67f516d9807857","datavalue":{"value":"isomorphism problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q716333$AD1B5C65-9EEC-4871-A746-3DD7012B6CC7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ac873341ab34d6db98676ef037e18583cae25841","datavalue":{"value":"oracle","type":"string"},"datatype":"string"},"type":"statement","id":"Q716333$A8EA1C7B-36F5-4895-9D83-49BC792B2957","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"214080879eb7024d2e09b1045af7950440b4363c","datavalue":{"value":"probabilistic computation","type":"string"},"datatype":"string"},"type":"statement","id":"Q716333$E0EE00AA-0369-4AB0-8CF2-81800520C383","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cd0a85fc687d5a2030ca309942325a5872eec67b","datavalue":{"value":"quantum computation","type":"string"},"datatype":"string"},"type":"statement","id":"Q716333$9AA1CA99-AB12-4754-8E3C-4DDFB0E84F51","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":"Q716333$5896098B-4735-4895-A729-570F9AA88FD5","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"50713fb6d53c11b0dd05bfee55abb36e7ae41009","datavalue":{"value":"https://doi.org/10.1016/j.ic.2011.01.006","type":"string"},"datatype":"url"},"type":"statement","id":"Q716333$84EF81D2-5AF1-4428-B853-E2840BD5C6FD","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"a8e8bab78f8ce8b431a69c0efe1a33311040c471","datavalue":{"value":"W2160461541","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q716333$5B32C259-F7B9-4C1D-8081-36AA2492A9CB","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"2cf248146407c89cd6f3a9dc1fd168eb97cade92","datavalue":{"value":{"entity-type":"item","numeric-id":3579214,"id":"Q3579214"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q716333$CE555906-5BFE-4627-B618-788740458085","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1234570f11caddb900135131d2fd06479f5792ac","datavalue":{"value":{"entity-type":"item","numeric-id":1772458,"id":"Q1772458"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q716333$AFA09729-A430-4456-80BD-1406C5799F45","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"50eead26665bf4327dc2785d2f3dfe4f076dc20d","datavalue":{"value":{"entity-type":"item","numeric-id":4507381,"id":"Q4507381"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q716333$84DD3550-A384-459C-BA71-F518CEE809DF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"85d4fb5cde811d6344089c826e86de340d1dd17c","datavalue":{"value":{"entity-type":"item","numeric-id":808692,"id":"Q808692"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q716333$7F2439A5-D561-4411-931D-DD501F116980","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"aed3243c6b21e043dc5a853f5918981fadd596b8","datavalue":{"value":{"entity-type":"item","numeric-id":1208403,"id":"Q1208403"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q716333$755EA042-1A75-4EDF-861F-062B75AD5347","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9d8653d2e6f53b17cedec7b9470bcf88609d4f1f","datavalue":{"value":{"entity-type":"item","numeric-id":5320667,"id":"Q5320667"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q716333$A9C628AF-8A7E-4D39-AA85-5D25728ECA4D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8a8ecf07a8a25a20eabf94efcc27f1a32b047fe9","datavalue":{"value":{"entity-type":"item","numeric-id":1575546,"id":"Q1575546"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q716333$24B80CBF-EBF2-40AC-86FB-F1AFBAE11298","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6c4b58f9e8478a4210509de111b81e4ccd911506","datavalue":{"value":{"entity-type":"item","numeric-id":4086709,"id":"Q4086709"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q716333$9D7FD31F-3B16-4D81-B616-AC4E1F72ECFA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"51bcc526bd248e68663c4d5cff17524f52ce59ea","datavalue":{"value":{"entity-type":"item","numeric-id":4520486,"id":"Q4520486"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q716333$2FB893AE-53A1-400F-809B-2CCD2471CB3A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c7a532846a2b2666b15e6ff83688ab5a0a9c2835","datavalue":{"value":{"entity-type":"item","numeric-id":4526969,"id":"Q4526969"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q716333$E722E88F-3027-4539-B29F-49223B562064","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e992429315736faf25dc16d657c2337beecd29ef","datavalue":{"value":{"entity-type":"item","numeric-id":1346615,"id":"Q1346615"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q716333$7AE6EC41-98BD-493C-B861-3574403E91E5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8b5a6160fa647abc427ca9901685f5c3070d764c","datavalue":{"value":{"entity-type":"item","numeric-id":3334985,"id":"Q3334985"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q716333$3B1EA5D9-4E91-487E-9781-5ECD216ECF89","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a5f2c613ba4e4163d44243004931f62c5b492055","datavalue":{"value":{"entity-type":"item","numeric-id":3334986,"id":"Q3334986"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q716333$26036046-295A-4A51-BED8-53AFF0797ACA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a41a23cfcd5e44f329acc4abc0eefe53035ea6cf","datavalue":{"value":{"entity-type":"item","numeric-id":3228627,"id":"Q3228627"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q716333$8D0681B1-E95F-411A-9994-992CD0A7410F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ac4b8e7cf4034c184fb2852754739a22a4e70036","datavalue":{"value":{"entity-type":"item","numeric-id":1108004,"id":"Q1108004"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q716333$214442CB-005C-4307-AEA7-0194227A10DA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cbf21b505b1db4cdc3a167da928476658c779f1d","datavalue":{"value":{"entity-type":"item","numeric-id":1961371,"id":"Q1961371"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q716333$A8512258-B822-4A94-9A19-99F1BDDE97BC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b41077c97b504be2e6ac56fb7b26543ed4cb1d08","datavalue":{"value":{"entity-type":"item","numeric-id":859979,"id":"Q859979"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q716333$323944F7-8E9B-4EFB-AA99-D1C4459D8771","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"651595b6045c6157b9e1cb45dd17869413d65f08","datavalue":{"value":{"entity-type":"item","numeric-id":1775885,"id":"Q1775885"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q716333$CD91827C-E912-46E9-82E2-4C787D62B6F7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"668c5b2da34a3aec680c0f5e66f9e4d87ccb409e","datavalue":{"value":{"entity-type":"item","numeric-id":1351599,"id":"Q1351599"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q716333$EE23B2B4-CC70-4B4C-B298-7CD440622F88","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dd6212e71e4e4adf824d10715a8233c427809ffb","datavalue":{"value":{"entity-type":"item","numeric-id":3581288,"id":"Q3581288"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q716333$92FBDC56-9748-47F7-9411-136EE6C84A7C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2c4151b452c4ed073bb1a3252eb241a98a885ce6","datavalue":{"value":{"entity-type":"item","numeric-id":3792624,"id":"Q3792624"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q716333$71891698-B37E-4689-BBF8-BA7CFA09068C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e51b8401e35df5fc023a4820101d20adab29b7f0","datavalue":{"value":{"entity-type":"item","numeric-id":1398366,"id":"Q1398366"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q716333$710D28CC-B2A6-4125-A9D1-48AB42D26ABD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3424c8121eb0ba4a3ce2e1a399746f525f187c8e","datavalue":{"value":{"entity-type":"item","numeric-id":3581285,"id":"Q3581285"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q716333$FA0F9E00-B988-45E2-8CD3-90F95D9408CA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8943ed123695e281545f9b7857e071f32021644e","datavalue":{"value":{"entity-type":"item","numeric-id":627189,"id":"Q627189"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q716333$D75BED52-18EC-46BB-B4DF-F0D4675334C5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7074782b19c76b4fa25b31b9a2a602ab866edd85","datavalue":{"value":{"entity-type":"item","numeric-id":705722,"id":"Q705722"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q716333$6E797B4E-E20E-4415-9CB5-2CE84F50B6B9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"382a064483edb64de89f16dc8222c044f55a2074","datavalue":{"value":{"entity-type":"item","numeric-id":4366883,"id":"Q4366883"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q716333$229411DA-6B2C-46F7-AF7F-73260AD311DF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c88c6be0a1adbfa3c68f0a5ba989620efb63f9e0","datavalue":{"value":{"entity-type":"item","numeric-id":5422486,"id":"Q5422486"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q716333$AFC42CE1-D7BC-4F7B-A549-8DEF4051AAC3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"060af8f3e101d9cd6773c46ed2fc74ebc353bcf0","datavalue":{"value":{"entity-type":"item","numeric-id":4895826,"id":"Q4895826"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q716333$926A914B-D04E-4D14-9EC6-DDE1A14B7B32","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ee4cc4a7ecc6049fce452aec78e65ad081d5e7ec","datavalue":{"value":{"entity-type":"item","numeric-id":4148000,"id":"Q4148000"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q716333$7A7D8F98-D0CA-481D-BEC5-96D92C1E2EB9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"65ffaa22dbe87f0e6a9f0e1ec7085fe7568cea0f","datavalue":{"value":{"entity-type":"item","numeric-id":2264677,"id":"Q2264677"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q716333$487E2FA0-8B7A-4874-A4A0-16C7D6230356","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4229113b68f8625a297254fc1cdaece10b287128","datavalue":{"value":{"entity-type":"item","numeric-id":5696935,"id":"Q5696935"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q716333$FD7379DB-3F0B-4168-A858-35A87B5FBCBC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e7208583f31490f719d0fa06f023572390252091","datavalue":{"value":{"entity-type":"item","numeric-id":4359460,"id":"Q4359460"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q716333$3F5BB599-0171-4EBD-BF05-F8924C08CFA9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"25aeb0cd6bad7e9ad25b8cbfaddfb36f51f9f34a","datavalue":{"value":{"entity-type":"item","numeric-id":3746906,"id":"Q3746906"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q716333$3B8869A7-1C1F-4C25-9945-85F9F118EB12","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4cded707123398ff6798a322d45de37a4390f5b2","datavalue":{"value":{"entity-type":"item","numeric-id":787674,"id":"Q787674"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q716333$702E2959-1693-4F28-BA8F-40F0BC687184","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5efe249d98b41f7083f97114d6fde0876628b49f","datavalue":{"value":{"entity-type":"item","numeric-id":1180408,"id":"Q1180408"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q716333$EBF6C5EC-9B12-43F9-93A7-BD81F8C8E2FA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f6bef531e3c54b91b631aa952c0ca63f0ac7db19","datavalue":{"value":{"entity-type":"item","numeric-id":1054475,"id":"Q1054475"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q716333$C8097D87-2464-4A0C-A3F1-F2C802E2C1C8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2120b12ab96678ee03b84909ec3e390673400419","datavalue":{"value":{"entity-type":"item","numeric-id":4210150,"id":"Q4210150"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q716333$964F5FBE-EFAE-4EA2-8617-D4A20291B45F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"485cc6d69595ee25d5b7dc9aa1852d47f28f4932","datavalue":{"value":{"entity-type":"item","numeric-id":5700575,"id":"Q5700575"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q716333$93BE7CD3-2409-4642-9EED-CFDFF8269AF8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e18e5b33c42a975e0ea884a76c83c33d5e131617","datavalue":{"value":{"entity-type":"item","numeric-id":4725752,"id":"Q4725752"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q716333$36F625F6-84DB-4A70-B435-54878341378C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ab289263ac80a8df854a0b026020c7e068e5240d","datavalue":{"value":{"entity-type":"item","numeric-id":1052094,"id":"Q1052094"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q716333$188C3A8C-E2E4-4F60-8C0E-A6A734E6E1DA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"175989e512d6162d2e23de4539fb227c102249ff","datavalue":{"value":{"entity-type":"item","numeric-id":4131647,"id":"Q4131647"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q716333$A405C9E7-F430-4D5D-8092-ED28369EC38C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"eae0a832743457f11dc96679e0a1657b112525de","datavalue":{"value":{"entity-type":"item","numeric-id":2819594,"id":"Q2819594"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q716333$ACBE583C-0264-44DA-AE14-497510BBBAB8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c3a445fad0dc0985d7853860e848fa4592ae7f51","datavalue":{"value":{"entity-type":"item","numeric-id":2706552,"id":"Q2706552"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q716333$ACF7587C-6FA1-4DE1-BB78-5D185F3398F1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f47b60ed99f09f3fb583f7fbaba6ba5893ee12a3","datavalue":{"value":{"entity-type":"item","numeric-id":3269139,"id":"Q3269139"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q716333$4B065C4C-21C9-41E1-95B0-304A42A7FBDC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"39fc746819d6a86d4542ba3a284ce0ca1127563e","datavalue":{"value":{"entity-type":"item","numeric-id":1135871,"id":"Q1135871"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q716333$6B138A4E-2DD6-465F-83D6-2B0E9AAC7504","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5a652fcc1099dcd9be0283890d4176019637c3d3","datavalue":{"value":{"entity-type":"item","numeric-id":4651491,"id":"Q4651491"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q716333$83A1EFAD-8E4B-4773-BCA4-E8D57437B79E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cca9920e80393926ef2e04c3761d37d8d8687f35","datavalue":{"value":{"entity-type":"item","numeric-id":2931408,"id":"Q2931408"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q716333$D3AE9211-43BB-45DD-AAE8-3CF8035DEAE2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1644b84d3838bf2933f19816a06e0772adad2efa","datavalue":{"value":{"entity-type":"item","numeric-id":1272661,"id":"Q1272661"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q716333$114D3D58-E69B-49D8-9332-44130EE9CFC5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"38f99c9040626540b18257b25ff5b59d89de1832","datavalue":{"value":{"entity-type":"item","numeric-id":4009812,"id":"Q4009812"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q716333$A26D846E-5E94-4CF3-96EC-6777B992838C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"527bc19ca28994e4f1cbc67acf1065ec21b6602a","datavalue":{"value":{"entity-type":"item","numeric-id":1329166,"id":"Q1329166"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q716333$BF83EAC8-E1D1-48B6-801E-EED24A15A052","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"105101dba9c28fafb7b0ccbfd4eb7b9c22c79810","datavalue":{"value":{"entity-type":"item","numeric-id":3343440,"id":"Q3343440"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q716333$025B2324-4690-4ADB-A766-40C0797DB21D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"68c982cbb5e59dc7e2ae30800c6f4d626a4d47b8","datavalue":{"value":{"entity-type":"item","numeric-id":4376179,"id":"Q4376179"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q716333$FC7A55FE-92EF-472E-86C2-A49FCCF7F3B0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bf854375ef6a956c526c0de5e533214f6344181a","datavalue":{"value":{"entity-type":"item","numeric-id":4376181,"id":"Q4376181"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q716333$4103F565-B97F-4A01-80D8-6D6849278DA0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"92dbd271da4abb6503ed890a2ba31e5fffa0b9d5","datavalue":{"value":{"entity-type":"item","numeric-id":3048248,"id":"Q3048248"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q716333$A6CB9FC8-4F06-42BF-A841-3F3394FC97AA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d545d46281c27f7c22d936768292713b57021712","datavalue":{"value":{"entity-type":"item","numeric-id":5617749,"id":"Q5617749"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q716333$50FFEDF1-599B-4AD8-B9E6-EF985D0854C4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5b85f17dbc0fffa49ba639b47837cdf4f61fd955","datavalue":{"value":{"entity-type":"item","numeric-id":3895641,"id":"Q3895641"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q716333$7E35DE0C-0617-41EA-B8F1-3D3BC9D1539C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c5a1bdebe5330a0bc43b4aecc19c865b4befee5e","datavalue":{"value":{"entity-type":"item","numeric-id":2542987,"id":"Q2542987"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q716333$3A0528A3-5D84-44AC-A6BC-777352031888","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8706e2a690d5177037c83ceb7a917b1bfcfb5f56","datavalue":{"value":{"entity-type":"item","numeric-id":4113883,"id":"Q4113883"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q716333$31F32FF9-9F4E-4867-975C-3854F0F5B0ED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3288e125d9c79bec61c2de501ba87bf7a229905c","datavalue":{"value":{"entity-type":"item","numeric-id":4035673,"id":"Q4035673"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q716333$C8ED158F-72FC-43EA-8E7D-B862BCDEB917","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"68f38456d84cb7476f9a6bc5209a99592a967b45","datavalue":{"value":{"entity-type":"item","numeric-id":1581496,"id":"Q1581496"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q716333$A053A50F-1F7B-4C57-9A28-52B50FEF98A7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fde012ef21d89edd10de7c33ccbb08320345d351","datavalue":{"value":{"entity-type":"item","numeric-id":3990656,"id":"Q3990656"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q716333$E7E87577-96EA-4E3E-87C1-DBC9A3EB8044","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c1dfd82bed9266a9eb9ee03c49c86a8c45cb2436","datavalue":{"value":{"entity-type":"item","numeric-id":1090454,"id":"Q1090454"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q716333$2E5F7C9D-FCBF-479B-BD82-13CEAFC60B26","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6c9c0ea30ffbefa60fb6a428d1b735f71dd473ce","datavalue":{"value":{"entity-type":"item","numeric-id":1112019,"id":"Q1112019"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q716333$FB74A5D6-C58B-4305-A16A-515E538F5342","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"7cf34961723f8f9d88efb326866c3859241fed7f","datavalue":{"value":"10.1016/J.IC.2011.01.006","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q716333$8E8D1F07-7BAD-4B34-940B-A2AC0214E2DE","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d7978021f06b3cc55ae1c6ab701e7f906b94fea2","datavalue":{"value":{"entity-type":"item","numeric-id":3334985,"id":"Q3334985"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c1272c0ebda1b9e130d268794525bf5b7a8fb243","datavalue":{"value":{"amount":"+0.8570609","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":"Q716333$1B1B9D59-D72B-44E5-9A0F-C10C73DA6B03","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"42e1dd5f18f3ccdea800fe3c78aef97d10b3c0f2","datavalue":{"value":{"entity-type":"item","numeric-id":3715098,"id":"Q3715098"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"47349905dd3c0f3423250bc48cdde51f20680c7f","datavalue":{"value":{"amount":"+0.73578864","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":"Q716333$31E597D2-680C-4B27-9FFD-5C198F328E0B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dffec52abc7491df39d7b262bd34e8a98d5ed4f4","datavalue":{"value":{"entity-type":"item","numeric-id":3172430,"id":"Q3172430"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3137010cbae0d0af2e5bf95abe3dfec07611bcd4","datavalue":{"value":{"amount":"+0.71868104","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":"Q716333$16AA0966-3B87-41B4-B434-3057C856B941","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"51bedb1d663b1b6c517c5170786204adabf528f8","datavalue":{"value":{"entity-type":"item","numeric-id":1431872,"id":"Q1431872"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f0ffc4c83c1874a97e64b16b4ad81997cb678cdc","datavalue":{"value":{"amount":"+0.7177604","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":"Q716333$C2985173-D990-4613-92D9-85544ED6E919","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bf6f5d85ae09272ad163a8b2f1129b51802b1e71","datavalue":{"value":{"entity-type":"item","numeric-id":3639061,"id":"Q3639061"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1bcef010ff31287ede8bb7df92d522871b6a0a35","datavalue":{"value":{"amount":"+0.71596944","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":"Q716333$3AC1B012-5CE3-4A08-9B1C-AE64A9E0DEDA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c5b67768fcf5910732d515f1259f28057313cd6d","datavalue":{"value":{"entity-type":"item","numeric-id":3829070,"id":"Q3829070"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"80230e10bbb6c0b5b62cd32a0bb8b22f459cec63","datavalue":{"value":{"amount":"+0.71590674","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":"Q716333$8DCBAF30-379B-4026-97F3-E222AE871538","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b1c27e18676494c3b772cc8d68917b05ce92fd27","datavalue":{"value":{"entity-type":"item","numeric-id":4913771,"id":"Q4913771"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5901cbf26143e1d4862e8eff24c1198cd9b0b315","datavalue":{"value":{"amount":"+0.7142786","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":"Q716333$DC2132CA-9A3C-4E00-8F1F-EA8E9B67AD2B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"34db3e8b62604b8fdcd714b654440592bd493ac3","datavalue":{"value":{"entity-type":"item","numeric-id":3675521,"id":"Q3675521"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1a2feb0eda4154137ee8931442ad1865e9f45c8d","datavalue":{"value":{"amount":"+0.7115908","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":"Q716333$82F73A34-A10E-4242-A074-93DA5C4A0BA9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"35c6e9a088f2dfb145cb5deabac7744551b959e9","datavalue":{"value":{"entity-type":"item","numeric-id":3085986,"id":"Q3085986"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"264da3be9086e95b20a72a86c35d8b9e2645c437","datavalue":{"value":{"amount":"+0.7109539","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":"Q716333$20774557-2239-401E-ACBD-B3A4FFC09DA8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"700ab51d884316120f97f77f312a7af95263292f","datavalue":{"value":{"entity-type":"item","numeric-id":4298369,"id":"Q4298369"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"33fc0e715d025b2897929f88aefc38d12f19f3de","datavalue":{"value":{"amount":"+0.71086925","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":"Q716333$EE71D735-7CB1-40B7-B42E-F61245278171","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Complexity classes of equivalence problems revisited","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Complexity_classes_of_equivalence_problems_revisited"}}}}}