{"entities":{"Q922707":{"pageid":924555,"ns":120,"title":"Item:Q922707","lastrevid":65405244,"modified":"2026-04-12T02:22:47Z","type":"item","id":"Q922707","labels":{"en":{"language":"en","value":"Subtree isomorphism is in random NC"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4170097"}},"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":"Q922707$1D8A96DB-B7A9-4253-AD67-1F46E90127C8","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"81137ac2d10424f09c4cdbd5e4d4cdfad82203a2","datavalue":{"value":{"text":"Subtree isomorphism is in random NC","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q922707$A33D6521-5D58-4885-BC28-905A9104379B","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"18bcf283cbfbf9ccc9e0289e537a77100a215af6","datavalue":{"value":"0711.68052","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q922707$D70CCF09-2467-4306-A772-FCA50FFB9160","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"51315c74d36db981f40fc971965c00b355af5f2f","datavalue":{"value":"10.1016/0166-218X(90)90081-M","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q922707$61BDFB2B-B5C3-4D00-AED0-6039367D9382","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"ae3141a18efbb496aff82e238abba7ed93d8d565","datavalue":{"value":{"entity-type":"item","numeric-id":676444,"id":"Q676444"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q922707$6617234C-7B73-4DF1-A920-EAEBEED09B25","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d7f03cf6abbdf2fe79063aacbf005af333537b97","datavalue":{"value":{"entity-type":"item","numeric-id":619905,"id":"Q619905"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q922707$F730A95A-F092-4F33-8AE7-890568929AF4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"09ef45db45b20ed04186cc047b8b30113586d9a0","datavalue":{"value":{"entity-type":"item","numeric-id":922706,"id":"Q922706"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q922707$DA2A5B44-008C-4BCF-B50F-F46F5F35A7BD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"29373d22cc965afe0313777aac5867e3ef096150","datavalue":{"value":{"entity-type":"item","numeric-id":1071802,"id":"Q1071802"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q922707$33BDF051-2036-4E29-A4B1-603B7979EFE1","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":"Q922707$B0CF05CF-4F3E-460A-9988-0FC0E7317AE9","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"70d2fbf8bcd48a5ca1ac752985098b379d0dbb65","datavalue":{"value":{"time":"+1990-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":"Q922707$E12E4DD0-8366-4078-913D-71D8BA058724","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"f2b230ccf1056844b5741d106acbedb3b33168a6","datavalue":{"value":"A subtree isomorphism problem is to determine for given two trees G and H whether there is a subgraph (subtree) of H that is isomorphic to G. Unlike other versions of the (sub)graph isomorphism problem this one is known to be in P, yet the existence of a fast parallel algorithm to solve it posses an interesting problem. The authors answer this problem affirmatively, provided that we consider randomized parallel algorithms. Their algorithm runs in time \\(O(\\log^ 3 n)\\) on a CREW PRAM using \\(n^ 3M(n)\\log \\log n/\\log n\\) processors, where M(n) is the number of bit operations required by a CREW PRAM to multiply two \\(n\\times n\\) boolean matrices in O(log n) time.    The authors start with the description of an algorithm for solving the rooted version of the subtree isomorphism problem, whic is then extended to the general unrooted case. Their approach is based on the best known sequential algorithm for this problem, given by \\textit{D. W. Matula} [Annals of Discrete Mathematics 2, 91-106 (1978; Zbl 0391.05022)], combined with the dynamic contraction technique by \\textit{G. L. Miller} and \\textit{J. H. Reif} [Parallel tree contraction and its application, Proc. Symp. on Foundations of Computer Science, 478-489 (1985)]. The randomized part of their algorithm is derived from using the randomized algorithm of \\textit{K. Mulmuley}, \\textit{U. V. Vazirani} and \\textit{V. V. Vazirani} [Combinatorica 7(1), 105-113 (1987; Zbl 0632.68041)] for constructing a perfect matching in a bipartite graph. Finally they prove that bipartite perfect matching is log-space irreducible to subtree isomorphism.","type":"string"},"datatype":"string"},"type":"statement","id":"Q922707$3EA876DA-2478-44DA-B529-B2B556718036","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"4418b7d4f2a0250db5c25bb23e561efd56a43eb7","datavalue":{"value":{"entity-type":"item","numeric-id":587571,"id":"Q587571"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q922707$8710C277-C27B-4A0C-BE3F-8801341620AD","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b65efe51b183d0f4a672427b8171cd1e14211cba","datavalue":{"value":"68W15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q922707$AE92A301-4ABB-429F-B1C5-BF5BDEB0A872","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q922707$47398263-9D38-4375-94A1-1FE282087516","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q922707$B246E13F-2905-429E-B59E-C926C8F14BBF","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"2d1ba7d1b3a6e13d5574f355d3908a8b386eea35","datavalue":{"value":"4170097","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q922707$E2886F56-6186-486C-A8BE-23F52A986B84","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1b2115df768887ca6e9de39978127792e655cff7","datavalue":{"value":"subtree isomorphism problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q922707$9623FDD5-1087-4CD6-A349-0D84DC77D55B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a4120140ca492bacbfbd6d42fbf271eccdc20544","datavalue":{"value":"randomized parallel algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q922707$DCD0041F-8FE2-4EA3-910E-C7FE6A194212","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"34f1528cd9548b088936bf54fdf77b3eb118e9bc","datavalue":{"value":"CREW PRAM","type":"string"},"datatype":"string"},"type":"statement","id":"Q922707$85D5EC8E-7B0F-4CB9-AFF7-5E7B5206428D","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":"Q922707$2FEF8AF4-8F04-4A88-BB96-E6C5D59BB6CF","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"0a6b13b2ba37a9810801d8784e6422607a5338cc","datavalue":{"value":{"entity-type":"item","numeric-id":4745254,"id":"Q4745254"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q922707$F0B345E4-4736-40F3-BB5C-6E756F721786","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a4077de5ad21c6b78a25ec43c56119974484a370","datavalue":{"value":{"entity-type":"item","numeric-id":4401551,"id":"Q4401551"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q922707$0442F7C0-F953-49A1-BC30-56F975C6493B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6a2ccaa8b67605d1442f748d22b53e4b3e37cf3a","datavalue":{"value":{"entity-type":"item","numeric-id":5564386,"id":"Q5564386"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q922707$C90651CF-4A09-42FC-8D8A-5AF84DFD5690","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"99dbf7521ede792694c93b1353b91b62425c92ab","datavalue":{"value":{"entity-type":"item","numeric-id":1262128,"id":"Q1262128"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q922707$BFBBF45F-BF31-425D-B945-5C664DA4CE37","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":"Q922707$8690BE0A-BCB8-474A-A8C1-A232D4BFD78E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"03784ff0aefef3971646719ef1ccf22220c25933","datavalue":{"value":{"entity-type":"item","numeric-id":3798258,"id":"Q3798258"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q922707$26B91802-553E-444B-BDB8-EAEE3485370A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f9b712e361bbfbc97c265dcc3e2463de06c2cf58","datavalue":{"value":{"entity-type":"item","numeric-id":1103639,"id":"Q1103639"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q922707$091ED1A7-BD96-4FDB-8159-C7E2129BB2F6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"df683643124679dcd0453572ee8d22f0d31fdfc3","datavalue":{"value":{"entity-type":"item","numeric-id":1115630,"id":"Q1115630"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q922707$8A513704-74CF-4CAF-8EDA-112FE0D5AFB9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"508894c78bd2770d073dbe57a0316a7e71f6bc30","datavalue":{"value":{"entity-type":"item","numeric-id":3890136,"id":"Q3890136"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q922707$37854752-323A-49C5-ACBE-5EFE8A4D834D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0f41d5e8d3c003ac9188dc5fb1f2879b5e9b1ecb","datavalue":{"value":{"entity-type":"item","numeric-id":4172071,"id":"Q4172071"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q922707$E7316B1C-DB96-488D-A9A8-BF2E98FF9EEF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ec62482a6f1abfd15d9d0aa6d0ca02f4b7a14835","datavalue":{"value":{"entity-type":"item","numeric-id":1095658,"id":"Q1095658"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q922707$8E460C43-A8C5-4D91-A2BB-A505657B5C27","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c4e877570eea6a31bd4bf800a8de151219d29028","datavalue":{"value":{"entity-type":"item","numeric-id":3732964,"id":"Q3732964"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q922707$3793EC19-5402-48F3-BF5D-F79C3A70A3EC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8f6d49f34b90554bdc2124202c77c3ea514e0173","datavalue":{"value":{"entity-type":"item","numeric-id":1244782,"id":"Q1244782"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q922707$C31CD9CA-35F6-4A0F-8994-A64A08D8F202","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bf662f3ea9ade9756d7d0b129beeab7ffca49810","datavalue":{"value":{"entity-type":"item","numeric-id":3031945,"id":"Q3031945"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q922707$EA37142A-A0FE-4439-BAF7-80C2A63742C0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"45693627939fec63d2836fa11bb5f307d8dbed5a","datavalue":{"value":{"entity-type":"item","numeric-id":3899517,"id":"Q3899517"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q922707$080875DA-FE4A-43CE-954E-9EBA6611BFBF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f450486e6dd81b9bc183a0057d83ff04fd2d4632","datavalue":{"value":{"entity-type":"item","numeric-id":3316595,"id":"Q3316595"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q922707$0B840D82-9399-4C67-B8E5-3BDCB7E55A00","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0c5477e08259683f4f1214eab272881c214067b5","datavalue":{"value":{"entity-type":"item","numeric-id":3694710,"id":"Q3694710"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q922707$E67BAF5D-7B47-4309-AE93-443030095851","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0fe58a947e4562a60ce9650461c6d3f1bf1df2ed","datavalue":{"value":{"entity-type":"item","numeric-id":3798258,"id":"Q3798258"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"16de874b086502a75594dc663b2329e5c790e5fc","datavalue":{"value":{"amount":"+0.9467039","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":"Q922707$1BD469AB-84E3-4340-867E-E9667F34AFE0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ddaa43ff349f0caabc4b21cfa01d4f7c97c01de1","datavalue":{"value":{"entity-type":"item","numeric-id":4935309,"id":"Q4935309"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"951293c299584bab243a5ad47075f3f1d715f899","datavalue":{"value":{"amount":"+0.8633198","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":"Q922707$DEC43226-F048-43AC-91AB-3DE757569851","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6427c72dbaf36d20367c7be167ed5fbea2b4f600","datavalue":{"value":{"entity-type":"item","numeric-id":1182123,"id":"Q1182123"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d613be690edb0d60fb6338159e540f6705e610d4","datavalue":{"value":{"amount":"+0.85887593","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":"Q922707$2F9B6982-8BE5-411B-8A3E-51EA3CA3577D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6159fbb53b0fe2daaa1b6d364724c5141361cf21","datavalue":{"value":{"entity-type":"item","numeric-id":1115630,"id":"Q1115630"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ca29b8bd183b4fa673c5c636be17d951ceb1d17f","datavalue":{"value":{"amount":"+0.8415478","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":"Q922707$3618C1AD-A058-48CB-A494-30DB3AA680A3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fafbaa85e135da3069a68977a9efd8d1bfdf9519","datavalue":{"value":{"entity-type":"item","numeric-id":3985812,"id":"Q3985812"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d40f45764208fb3d7e1dcca661822d8d9eb01170","datavalue":{"value":{"amount":"+0.8295869","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":"Q922707$3C5C6CD6-DF81-4A40-8367-C925F9E7A1B6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b118cef682311639c18907c27e8f613d9705dbab","datavalue":{"value":{"entity-type":"item","numeric-id":1387834,"id":"Q1387834"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2b0a57222803729929b4fbfb28a674653eed19bc","datavalue":{"value":{"amount":"+0.8163824","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":"Q922707$93C58610-49B9-4E78-8EFB-6C97D1A6C57C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f5f0cfcd5abe6561f8c25227f0852647bc751d7a","datavalue":{"value":{"entity-type":"item","numeric-id":1183481,"id":"Q1183481"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b038d87f0b826b8907d1218645802ef0253a4f7a","datavalue":{"value":{"amount":"+0.81279755","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":"Q922707$F6233E86-7B40-41C5-8013-844F506F428F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"980c1614494ed38ffba77b4fce25e457d223f053","datavalue":{"value":{"entity-type":"item","numeric-id":3359785,"id":"Q3359785"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e6d9f5e1c2392bdee1426f48f694b6f1ae08ee66","datavalue":{"value":{"amount":"+0.80992377","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":"Q922707$D8E25A8D-46A2-4918-87D4-CF4DE092E19D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6eae4b1954257c19e61371e63bebcd0d9f593b03","datavalue":{"value":{"entity-type":"item","numeric-id":4575669,"id":"Q4575669"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c958d278bbbf0b90ba38b69a39bdb73dadfdb02c","datavalue":{"value":{"amount":"+0.8052343","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":"Q922707$D5C4C627-7209-4D1B-B659-174927C47DAE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"35ab2a54aa8fa97a7393c4f0ef3367468f464c28","datavalue":{"value":{"entity-type":"item","numeric-id":4554355,"id":"Q4554355"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a287af2c6023f61c1393d9466273b00659664c2c","datavalue":{"value":{"amount":"+0.80048037","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":"Q922707$F410B486-010B-4982-BBEE-61DE20B41FC0","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Subtree isomorphism is in random NC","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Subtree_isomorphism_is_in_random_NC"}}}}}