{"entities":{"Q2908861":{"pageid":2919586,"ns":120,"title":"Item:Q2908861","lastrevid":51537827,"modified":"2026-01-18T17:00:47Z","type":"item","id":"Q2908861","labels":{"en":{"language":"en","value":"Graph isomorphism is not \\(\\mathrm{AC}^0\\) reducible to group isomorphism"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6073542"}},"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":"Q2908861$E0EF2311-8484-452B-9099-7B678FC2314E","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"8362be42626b504c6ede34ffffe1b2400f4de5df","datavalue":{"value":"1245.68101","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2908861$BF1117AC-DADD-4AA2-860A-C18BB4CB6DDA","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"144bf1814e22a6734bd0f619d9bcf126ff436af1","datavalue":{"value":{"entity-type":"item","numeric-id":2229710,"id":"Q2229710"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2908861$729A246E-9B9D-4EF3-8CD0-C340E0DDCFDB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"efa0ee16bcf9d62945fa4e27ea47d07c341ed7b6","datavalue":{"value":{"entity-type":"item","numeric-id":1114674,"id":"Q1114674"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2908861$1958031E-E468-4467-9847-B64E07FE9536","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"f223dd58616c767aec7eadfe0a09977c13567f44","datavalue":{"value":{"entity-type":"item","numeric-id":6050524,"id":"Q6050524"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2908861$99643F89-6A5B-43A4-92F3-655D2686CC9D","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"8ce614070009b11291ee6b015c78682bf76dc525","datavalue":{"value":{"time":"+2012-08-29T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2908861$E2A36830-B967-4502-BE0F-8D86A1F9B2E3","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"d5119ff076ef5f6c214149ed51667376b81291f5","datavalue":{"value":"http://subs.emis.de/LIPIcs/frontdoor_bb62.html","type":"string"},"datatype":"url"},"type":"statement","id":"Q2908861$B7663B65-4991-4CDB-9F3C-320DB8ACDE8F","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2908861$5049D90B-FFED-438C-A9BC-7972A99AFE02","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b4346faa01bb5fb0576370374d6456afd58d5666","datavalue":{"value":"68Q15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2908861$91AB7311-24D3-4A6F-8689-054DCD276AF2","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"d389ef405637af0d0846d19d3fed4b9e7f4abedf","datavalue":{"value":"6073542","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2908861$BDA5D8D2-A455-4AFD-A1B6-7AE74296E6CF","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c5f8382ba04f9f05f645b4d0e4b9ea28f0619583","datavalue":{"value":"complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q2908861$0F02ED15-AF97-4E99-A98B-F2B5FCEFA500","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"05e4426c0eeaebb3adea92ee2b814be8271c6157","datavalue":{"value":"group isomorphism problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q2908861$D6899BA5-CA0F-41FC-8397-5F47CF37B16D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"981430382d3dd23a614a0e49be2feaa549aa8384","datavalue":{"value":"circuit com plexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q2908861$8B8BF66C-9FE4-4299-B193-6D7F84186743","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":"Q2908861$0232BC82-B760-4BBA-B76E-49FE36DAE4ED","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"08c65f26d68be3618f07854b8b87642b882055ff","datavalue":{"value":"W2120674923","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2908861$06732C05-8AC6-45EC-BA70-69B9341E8A63","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"540ed64821ec8dd5b04cc30161d7eec6574dd0ad","datavalue":{"value":"10.4230/LIPICS.FSTTCS.2010.317","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2908861$A6F332C8-0346-42F3-89B6-5923B73A013E","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"a7cc3f13c0791486f386e3f60795c8c990cdcb53","datavalue":{"value":{"text":"Graph isomorphism is not \\(\\mathrm{AC}^0\\) reducible to group isomorphism","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2908861$CDDF5024-61D6-476F-9D60-097B474CA9F4","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2717632e7ef3331a4fc01f6331daa4dbda583e11","datavalue":{"value":{"entity-type":"item","numeric-id":2947584,"id":"Q2947584"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f0a2c0f47219aee9eade1f799ce08e074145b8cd","datavalue":{"value":{"amount":"+0.9885509610176086","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":"Q2908861$8A80CDB2-1ACF-434A-B3FC-C954F0B44FBD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5bdd8a891387908419cb661cc84035e96e7503b9","datavalue":{"value":{"entity-type":"item","numeric-id":4651507,"id":"Q4651507"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fafba648975c3041047d2d0a6a92a95aa26a4073","datavalue":{"value":{"amount":"+0.8059457540512085","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":"Q2908861$998C201A-C686-4719-BDB2-A7C7E4860D05","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"53ffd89c337139b073d311d6fd28f173efccc357","datavalue":{"value":{"entity-type":"item","numeric-id":5458831,"id":"Q5458831"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"68e7db8f6c1f16d9aa478edd237c801325486db5","datavalue":{"value":{"amount":"+0.7993186116218567","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":"Q2908861$80E56218-614D-4AAE-9006-5BA73E779F65","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b7ff349add6f467c81329e125c3a70196385973b","datavalue":{"value":{"entity-type":"item","numeric-id":987394,"id":"Q987394"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c1967fb11f56f37103b65334a1408c80348d1646","datavalue":{"value":{"amount":"+0.7944320440292358","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":"Q2908861$CFAD02C8-1BFE-4C89-A709-B366EF0CFC8C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f626116fa61005e7c9c9fd7c473424f0d5885665","datavalue":{"value":{"entity-type":"item","numeric-id":5361871,"id":"Q5361871"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fff7b228ca629f61d7db6456728c606ce44e60ee","datavalue":{"value":{"amount":"+0.785524308681488","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":"Q2908861$F7CC77DB-9833-4F43-B804-C2D69E37D246","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2908861","badges":[]}}}}}