{"entities":{"Q1332763":{"pageid":1343507,"ns":120,"title":"Item:Q1332763","lastrevid":46274676,"modified":"2025-12-24T11:23:35Z","type":"item","id":"Q1332763","labels":{"en":{"language":"en","value":"Counting trees in a graph is \\(\\# \\text{P}\\)-complete"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 633506"}},"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":"Q1332763$E4624B76-4DD9-4407-896E-0F9FF673FC15","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"650e84a94081f051c748ebdb94158193be3c4684","datavalue":{"value":{"text":"Counting trees in a graph is \\(\\# \\text{P}\\)-complete","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1332763$6D1973FE-9EB6-4C1A-BDAB-9BE80507FE89","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"8372544465de26ec2f1f38a3968d1113bec0b5fe","datavalue":{"value":"0809.68076","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1332763$9B60A72D-7E17-44BE-8A7D-D0527E2D8337","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"9117195a4e8c4affbb9c5c78cc760a7feced255f","datavalue":{"value":"10.1016/0020-0190(94)00085-9","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1332763$5BA8980C-8FCA-4E7D-B7E4-424B8518A594","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":"Q1332763$8CB3EECE-E0D6-4B81-B7E1-EC5E0DAAFA9A","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"84681ccfddfaace3f47555c1fcea3a9191c156fd","datavalue":{"value":{"time":"+1994-10-13T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1332763$BC3D51CA-F90E-41FC-B765-4647D3E34A4F","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1332763$7F7B3680-06FF-4387-A10F-763674FCCC0F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1332763$BDA273BB-9EFF-4784-8782-2AC5BE007425","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"1de0493fc6f7fe4361a54e7c2f5546e4ec52adf0","datavalue":{"value":"05C30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1332763$D4320E1C-2366-4B7E-86CF-0642DB27F8D7","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"4eb3dd136b4ab3f2ccc4c7517d33dc2dc4eaeaad","datavalue":{"value":"633506","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1332763$314F955E-FAD4-49CD-AC96-30A95300522F","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2ba0cc3f7aaac8445724ef309c9eecb57f5a563d","datavalue":{"value":"computational complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1332763$8808F093-B856-4032-9659-441B9232A64A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ea4adf12ab573f9dcfa5d60187ded62e3f048fae","datavalue":{"value":"combinatorial enumeration","type":"string"},"datatype":"string"},"type":"statement","id":"Q1332763$ABF10D96-472B-45A9-9A01-47C34BBA7761","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"133e8b31581cc0bba35e289b44b7a21bd0acf90d","datavalue":{"value":"\\#P-completeness","type":"string"},"datatype":"string"},"type":"statement","id":"Q1332763$54479007-F863-4CA8-B28C-5AF9614795E8","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"6e3a8f9108e3ef9a34953b0578b0aef803753406","datavalue":{"value":"Q56083439","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1332763$0722E6B3-2C8B-49CB-82C2-3674C39EF084","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"871bc74022ea4f6f28f92d19fa6227a3c4413324","datavalue":{"value":{"entity-type":"item","numeric-id":1058289,"id":"Q1058289"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1332763$5E65F644-D300-4731-ADA6-07A61F03ED8C","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":"Q1332763$8F9DE9D3-ABAC-4537-816F-84A99BA72BC3","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"255eca5984d864539cd28226b8018a23480a4a9f","datavalue":{"value":"https://doi.org/10.1016/0020-0190(94)00085-9","type":"string"},"datatype":"url"},"type":"statement","id":"Q1332763$CD61F599-59F9-48D8-A2D8-CC85E67D6712","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"3c0101c5b559328c24ee724d170d612952c63337","datavalue":{"value":"W2053566189","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1332763$51E38F5B-A01B-4C73-86F5-F7416C3DDDE8","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"b2b7958dc2b7884b86126cf911b9071d9ab73aa9","datavalue":{"value":{"entity-type":"item","numeric-id":4115165,"id":"Q4115165"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1332763$8DBF0B3C-FA6B-4F44-BB18-AC1AD7D13ABA","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":"Q1332763$D59A7992-1131-47C5-9B6F-F02F77DE948A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"70536879af054717c0f3d9d913a10e93c328980d","datavalue":{"value":{"entity-type":"item","numeric-id":3853129,"id":"Q3853129"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1332763$DAB4FC3A-0D17-48EE-9D3C-DC186959719E","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6ab0bcbff5204f5485b715219dd9e424ba978fcc","datavalue":{"value":{"entity-type":"item","numeric-id":4504966,"id":"Q4504966"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"eec0ae0abd8eabe6150480e91299f9d378bb7f0b","datavalue":{"value":{"amount":"+0.8977715969085693","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":"Q1332763$432546CC-DF2D-4DD4-AB94-6EB390C923C9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b1c7091e14c93f3d6ac2e9e1319c12eb75d03961","datavalue":{"value":{"entity-type":"item","numeric-id":1883389,"id":"Q1883389"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"29089e9de1422645c13ede08acbe072378bd71c8","datavalue":{"value":{"amount":"+0.8267402052879333","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":"Q1332763$1728E720-FB05-46C6-852F-4F38EE5C5C02","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7ed14b01f9a0795b14681edf546609e3148747d9","datavalue":{"value":{"entity-type":"item","numeric-id":1058852,"id":"Q1058852"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fe2a1b6270a38f5d4a0bc5075c73ade30cd69ed0","datavalue":{"value":{"amount":"+0.8256064653396606","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":"Q1332763$4683B71E-17C5-4182-B21D-A65CAECED4AC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"43c650ec002ab5f9f06c3d706fc8572fdb2164f7","datavalue":{"value":{"entity-type":"item","numeric-id":2862211,"id":"Q2862211"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8bd7791e9e9c66634cf88c193cf6a0ac10f9af7f","datavalue":{"value":{"amount":"+0.8123448491096497","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":"Q1332763$91939D91-7843-4BE0-9F67-BD258E8C7819","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d9c02d5d91aaf998118524bd7578cc25ca859afb","datavalue":{"value":{"entity-type":"item","numeric-id":2784460,"id":"Q2784460"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"948f6e09febabb5ade61ae0ea43ec38cc32b3019","datavalue":{"value":{"amount":"+0.8088834881782532","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":"Q1332763$F48AD3DF-E819-4939-A780-D3F879311530","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1332763","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1332763"}}}}}