{"entities":{"Q5737815":{"pageid":7767369,"ns":120,"title":"Item:Q5737815","lastrevid":52817885,"modified":"2026-01-23T13:57:07Z","type":"item","id":"Q5737815","labels":{"en":{"language":"en","value":"On the \\(\\mathrm{AC}^0\\) complexity of subgraph isomorphism"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6724228"}},"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":"Q5737815$ED23E03C-590F-4B7D-A06C-4C304FFC0E70","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"63f81ed0f9e3a7c394fa8e7842eef55b39c9ffe3","datavalue":{"value":{"text":"On the $AC^0$ Complexity of Subgraph Isomorphism","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q5737815$BEBD7D7E-7139-47E9-9171-6B4FAC2AEBB8","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"d9309843b97cef0c9b13623ae64fb7027be518e1","datavalue":{"value":"1370.68135","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5737815$8291C32C-2D10-49BA-A9AF-BD009A72285D","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"33a80958f34af1360a20ec52a8d32aac622cc688","datavalue":{"value":"10.1137/14099721X","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5737815$DFBD406F-A24A-4424-AF07-8B0F9691CD8F","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"23e97eaa08b13e1bd8cce4634bd30e888245cab0","datavalue":{"value":{"entity-type":"item","numeric-id":648967,"id":"Q648967"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5737815$AECC1403-5CD0-4196-8B6C-0D8B96C21E84","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"df23bf7926ba5bb7cff51fbeeb73a5231d5cbdc9","datavalue":{"value":{"entity-type":"item","numeric-id":590705,"id":"Q590705"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5737815$3215E671-EBFE-4F72-B410-760241CEE368","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"7c0bcfb4eb9a7ab6903b269f394ffde6834d9319","datavalue":{"value":{"entity-type":"item","numeric-id":1370854,"id":"Q1370854"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5737815$78F42BC8-AF40-4C02-A813-1723D1BEF069","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"c2a1c45d0f0997786c62faf9f7fcd603424632e8","datavalue":{"value":{"entity-type":"item","numeric-id":84798,"id":"Q84798"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5737815$83BE5B49-343F-4924-A253-D47E651BCB47","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"38165a9d8656cc51a51d42826fe75b9a3e52602c","datavalue":{"value":{"time":"+2017-05-30T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q5737815$F57FAAF1-E3EF-4206-A5A5-F280C3014AEB","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5737815$D489FFA8-AE88-4E13-B403-B32EFC87D76B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5737815$915238B0-21E7-4000-B1BF-E5F53ADC4E64","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"2e742a171e2cc4a4f154f55124e2a34e0da3eb3e","datavalue":{"value":"05C60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5737815$FFBE6669-20A1-4D0A-BB67-AE076DDC4F7F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5737815$522FDDD0-E6BA-4ECB-82B8-3FD4E6DC5065","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"8f5833bf8386a82be65643dda3a8a9df9382c9cf","datavalue":{"value":"6724228","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5737815$1531B63E-3A88-44F6-9650-BBF33CC832CA","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"67356e578728b6957d374bbb1825497ae0fbc477","datavalue":{"value":"constant-depth circuits","type":"string"},"datatype":"string"},"type":"statement","id":"Q5737815$586AF68C-194C-4990-9B6F-0E5967779063","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e50d5f5383452bd2adcef1d921f570ccfd70e04f","datavalue":{"value":"subgraph isomorphism","type":"string"},"datatype":"string"},"type":"statement","id":"Q5737815$AE787978-A637-4D8A-B978-EA80B0C98720","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9328bb53dda67205bd6b700853332eb4620fbab7","datavalue":{"value":"threshold exponent","type":"string"},"datatype":"string"},"type":"statement","id":"Q5737815$9545CD11-1708-4234-AA41-94A706E8719B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d57d68ed777850433efcc3de197edd817953ef26","datavalue":{"value":"treewidth","type":"string"},"datatype":"string"},"type":"statement","id":"Q5737815$09CB3D5D-0E91-4608-8147-3306A819863A","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":"Q5737815$3CC19B8A-3421-47DB-AFE1-6E5BC16DAC21","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"99725c8075de63c7bd6b763d57e2592f23449e8e","datavalue":{"value":{"entity-type":"item","numeric-id":3094934,"id":"Q3094934"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5737815$AC56264E-351A-484F-9156-DC020B4CA950","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0bbaef82e8eb92dc4676d651d32794ea23b80ec1","datavalue":{"value":{"entity-type":"item","numeric-id":2798999,"id":"Q2798999"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5737815$37ED2D9E-6F7C-4840-A3C9-295F33DD46F2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"42451d9b2f091244b010a7dc1fc6a0f53a57abc4","datavalue":{"value":{"entity-type":"item","numeric-id":4369883,"id":"Q4369883"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5737815$8B16E039-EDD0-4A15-814D-92823AD4C829","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8a774b6029c9da3ff517fc7d194393fbcab2285b","datavalue":{"value":{"entity-type":"item","numeric-id":626676,"id":"Q626676"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5737815$E5EFEAA8-30D6-44BF-AD87-4373610E028F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"927616c149dc228fc931ad829d8a8c0aea8f2a14","datavalue":{"value":{"entity-type":"item","numeric-id":4002919,"id":"Q4002919"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5737815$B328FA5B-54EF-4994-AB21-2054228D73D8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fdc1515d44020b1debe70a59f43f85399130fb1c","datavalue":{"value":{"entity-type":"item","numeric-id":5711519,"id":"Q5711519"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5737815$499A3C17-2AEE-443D-A317-EABB9127B043","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3e20c121fc61df169000a4a3b317e3de8556d575","datavalue":{"value":{"entity-type":"item","numeric-id":4294576,"id":"Q4294576"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5737815$F79D4057-020B-4462-8796-F50A78B79A99","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2ef7f0a49322d7e00ccf966a4a703f60f5caeed1","datavalue":{"value":{"entity-type":"item","numeric-id":5259539,"id":"Q5259539"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5737815$238096EA-6E55-41B1-BC2E-1C5BC828290D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1f73fbf65a5563c2cdba7da3e67294bc6a131fbe","datavalue":{"value":{"entity-type":"item","numeric-id":4635616,"id":"Q4635616"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5737815$4659140B-6AE7-4844-A0AD-FBC3FCBF2A6B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6327224c4debc2501c4439bfd0d53425e1e3cd69","datavalue":{"value":{"entity-type":"item","numeric-id":4505015,"id":"Q4505015"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5737815$5483634B-02D1-4D44-B7F2-D394B807B9B3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ff5e2bb90c8cf8d80fb6cdd156087f7560a367d5","datavalue":{"value":{"entity-type":"item","numeric-id":1578412,"id":"Q1578412"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5737815$20A5ABFE-131B-4EAF-BF9C-5CD727E4A75B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"69e401ff965d2eb2630d56b4dc5431ee73f6ac35","datavalue":{"value":{"entity-type":"item","numeric-id":3624379,"id":"Q3624379"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5737815$47CEF962-8B40-4A3E-9536-2C05247EF0D0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"90870b52f69b79e9f1be8991c81685fd47daf61f","datavalue":{"value":{"entity-type":"item","numeric-id":3546332,"id":"Q3546332"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5737815$08D1A724-32DE-4F1F-8465-4061888B0B1C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0d396299693e4f28921602182db43542ab4b6d60","datavalue":{"value":{"entity-type":"item","numeric-id":2519023,"id":"Q2519023"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5737815$D7B595CA-65A3-49A3-9C31-5DC250ADEF4E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"415bf483704832dfb1db3c30f31c6afc6a0cd336","datavalue":{"value":{"entity-type":"item","numeric-id":1322486,"id":"Q1322486"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5737815$11AA6025-1316-4C71-AF32-052503AF7683","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bcc85ab9fa16bca6fc418f173746a68af16e1d0b","datavalue":{"value":{"entity-type":"item","numeric-id":3977078,"id":"Q3977078"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5737815$09AB43F8-D6B0-4BAC-A511-018D2E5ABB1F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"26fa1ffd0efefc54237f6718f7833e7e8b37a4e5","datavalue":{"value":{"entity-type":"item","numeric-id":1323513,"id":"Q1323513"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5737815$971CB950-C719-4498-B34F-3838D8833B1C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"28588578bb09af0b4bf0a3281ab6c8d321eb619b","datavalue":{"value":{"entity-type":"item","numeric-id":4519896,"id":"Q4519896"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5737815$A20DA6C9-14D7-4403-8B61-CAFF21F8EE81","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8e42c9128d887844233caee1df2a5e2ba33f6baa","datavalue":{"value":{"entity-type":"item","numeric-id":642463,"id":"Q642463"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5737815$52E1201B-9774-45AD-B96D-2F23E262CAAD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bba75b1fcf7bdfc096d3519487d870ba27bfb198","datavalue":{"value":{"entity-type":"item","numeric-id":3002818,"id":"Q3002818"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5737815$73E67D99-D04E-40BB-8CA9-103814B2688F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"816958e4557d45e7d4a014a4eb6b7111e4cc97ac","datavalue":{"value":{"entity-type":"item","numeric-id":2965515,"id":"Q2965515"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5737815$FCD965A2-1C3A-44DF-848E-0C55E7A599F6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"06789ff9711fcfacc05dca59cf6af8d93e612f92","datavalue":{"value":{"entity-type":"item","numeric-id":2931403,"id":"Q2931403"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5737815$157B127A-01F1-4C56-8C47-012CCE76D0ED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a5085dbbcc1ce6fb384f8e79821c14c915008881","datavalue":{"value":{"entity-type":"item","numeric-id":4028099,"id":"Q4028099"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5737815$D38C94CB-B9C8-454D-BC73-E87AD4980B76","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7e62926166610e171255ba7600cdacbb982331e7","datavalue":{"value":{"entity-type":"item","numeric-id":1179473,"id":"Q1179473"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5737815$85F903EC-FF43-43E9-9199-C40C3BA0B953","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"422191f7fa8b2d64e6ff41dbfa56ea42d38984ad","datavalue":{"value":{"entity-type":"item","numeric-id":5302097,"id":"Q5302097"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5737815$AA30671C-A200-4233-B762-C175FA8DF3B5","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"e1d93ece99b3b63710704b4369b50a1195815376","datavalue":{"value":"https://doi.org/10.1137/14099721x","type":"string"},"datatype":"url"},"type":"statement","id":"Q5737815$13F38E39-B626-4C0B-AC4F-7330CBF3951F","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"574d2662a3030dea4dc42f21c1303659e059b006","datavalue":{"value":"W2618244641","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5737815$163709A1-283B-4E0C-B441-F089BF488A61","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"928577ff746849f9a4884cffe3f2f9eaeaf289b9","datavalue":{"value":{"entity-type":"item","numeric-id":5875558,"id":"Q5875558"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7d77278cfeb8fba8120b5ac3a110888197e4bf9b","datavalue":{"value":{"amount":"+0.8522142171859741","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":"Q5737815$7E753BD6-42FB-43C9-98B0-4C29FE6AF15D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cc747dc710cd924e0ed858a5d965c8da8f532f1a","datavalue":{"value":{"entity-type":"item","numeric-id":2041983,"id":"Q2041983"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7da1815b272ea0eae0f99fa14d0939ea7d534547","datavalue":{"value":{"amount":"+0.8517333269119263","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":"Q5737815$1554E8E9-B936-4C4C-BE37-AF8462451F64","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7384869f2236c7f12d0dfc56bea9acbfeac0404a","datavalue":{"value":{"entity-type":"item","numeric-id":5122162,"id":"Q5122162"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e1869d7c5caf69c56e5c79ff8a8b4de6e0fef97d","datavalue":{"value":{"amount":"+0.8078786730766296","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":"Q5737815$D57D22B1-D3DE-4E53-9784-BE34FB8CB39B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"92c488d1e250378c1dc0d704fd6af47c75c86cd2","datavalue":{"value":{"entity-type":"item","numeric-id":626676,"id":"Q626676"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b45963dd2f71361b61b73350f89d6843d569e6f4","datavalue":{"value":{"amount":"+0.8017189502716064","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":"Q5737815$163E727A-D8C2-498D-9AFC-A1A3F14D362E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9cdcbb8ad625b74732552a62d272336ef2f20653","datavalue":{"value":{"entity-type":"item","numeric-id":888440,"id":"Q888440"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fd3d0cbc6d0d586509d7ad7b0ad11ca17e79eac6","datavalue":{"value":{"amount":"+0.7735908031463623","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":"Q5737815$EA1CAB79-6E13-424C-995A-DAB23C2AD0E5","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:5737815","badges":[]}}}}}