{"entities":{"Q686299":{"pageid":688148,"ns":120,"title":"Item:Q686299","lastrevid":63609048,"modified":"2026-04-11T14:19:44Z","type":"item","id":"Q686299","labels":{"en":{"language":"en","value":"Tutte polynomials computable in polynomial time"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 428137"}},"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":"Q686299$9D6159F6-13B4-4E53-A536-AF917327C574","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"53a2a0e935d8256772c61969a226cb61a6eea63e","datavalue":{"value":{"text":"Tutte polynomials computable in polynomial time","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q686299$58D9D50A-20ED-4810-9E0C-EFA19BD3C221","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"a6259ca04dbc52001ed07f5ad63ba93f8ac41743","datavalue":{"value":"0780.05011","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q686299$FADD1164-1B91-491B-9FF7-73E3B0578B72","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"5046609efd7b958945b365d0ca789812bf0b945c","datavalue":{"value":"10.1016/0012-365X(92)90289-R","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q686299$E4251202-7DE5-49EE-B656-CFB5DA7A65ED","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"38665fe4ed2b835132254a58832c329597060029","datavalue":{"value":{"entity-type":"item","numeric-id":175483,"id":"Q175483"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686299$476E494E-3F21-4C7C-B90A-2D579E3E8F4E","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"75a8b7e8c6887771540dbf878c1b8ed98975502d","datavalue":{"value":{"time":"+1993-10-14T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q686299$B1C40FC6-23D0-4642-8675-C7655795A71F","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"05cec3bfe874822780ddc030e0d9feaf7b97628b","datavalue":{"value":"Determining the Tutte polynomial of a matroid at a fixed point \\(P\\) of the plane is known to be \\(\\# P\\)-hard unless \\(P\\) lies on a certain hyperbola or is one of 8 special points (\\textit{F. Jaeger}, \\textit{D. L. Vertigan} and the second author [Math. Proc. Camb. Philos. Soc. 108, No. 1, 35-53 (1990; Zbl 0747.57006)]). The authors show that for any accessible class of matroids of bounded width, the Tutte polynomial is computable in polynomial time. Series-parallel matroids have this property (while the above \\(\\# P\\)-hardness was proved for cycle matroids of planar graphs by Vertigan). The problem remains open for bounded tree-width.","type":"string"},"datatype":"string"},"type":"statement","id":"Q686299$953E2C4F-7A3A-41A3-BEDD-6B3D0880079A","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"3a2423d4080d6028a3a8be7e0d0098fe6e3cd478","datavalue":{"value":{"entity-type":"item","numeric-id":226827,"id":"Q226827"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686299$01258C5D-9CD5-478A-B7CA-847F91022B4A","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"a06727f99c93aa58e84e3d476d4f6a1bed523458","datavalue":{"value":"05B35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q686299$2C649B85-402A-4534-8367-BB182E3DF841","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"1542c79c0e7445541d5e8648f26978e49c1ef27b","datavalue":{"value":"428137","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q686299$62EBB5E1-CDE2-4282-83B5-71FBD047B27E","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1976f1378c55759244812e0b3a3c899c56ea76c9","datavalue":{"value":"Tutte polynomial","type":"string"},"datatype":"string"},"type":"statement","id":"Q686299$FB412B45-4BB2-4488-B726-D23AB826B147","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e172629663780e971698d7d841046893adba3be5","datavalue":{"value":"matroid","type":"string"},"datatype":"string"},"type":"statement","id":"Q686299$7766A9AA-5445-4B20-A520-D8A2B3F6D1D4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a862f016acc1e519aa7b6644887bfca464692961","datavalue":{"value":"polynomial time","type":"string"},"datatype":"string"},"type":"statement","id":"Q686299$40EAA43A-74BD-4031-92A5-72BDB2347711","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"034c7d0367010a69cad626c2aace24589e714eeb","datavalue":{"value":{"entity-type":"item","numeric-id":580347,"id":"Q580347"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686299$799E9AC5-9859-46FE-980A-8FB3F9768FA0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"40080f4b81a5e9c3a14af20f9731645e9403a640","datavalue":{"value":{"entity-type":"item","numeric-id":1369654,"id":"Q1369654"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686299$4CF9C51E-BC85-427F-A21C-AE202F1125BE","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":"Q686299$6A27AAEF-A7D5-4389-8D42-92E74F3D302A","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"f96a660eaa4e8b33419c867ffedb789edb466ebc","datavalue":{"value":{"entity-type":"item","numeric-id":1116705,"id":"Q1116705"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686299$D218E725-7CEB-4854-A234-2185E5C15D89","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e17077402b9f6b244118635ed5768857c3920b88","datavalue":{"value":{"entity-type":"item","numeric-id":3909066,"id":"Q3909066"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686299$275442A3-EFFF-4CAA-A1D0-4A88255C8FFE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9825a31e740bab9f13786d4564e931fa63ffe7c7","datavalue":{"value":{"entity-type":"item","numeric-id":5618392,"id":"Q5618392"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686299$F0D1C383-C6A2-43F4-80F4-CF0C35442023","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"86f3a056f18370884ef8dba1c5001b512b35dc95","datavalue":{"value":{"entity-type":"item","numeric-id":2936844,"id":"Q2936844"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686299$B817A3AD-0797-4636-8B50-B6CF7357CF68","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"87e9745de40f5ef74f49f0b6349fa57915c50dbf","datavalue":{"value":{"entity-type":"item","numeric-id":4012032,"id":"Q4012032"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686299$2A62287D-ACDA-4207-9D94-1DD1FBE3C632","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d81dd79a1bed14cc9a639b53e9dbf2064e63ac1c","datavalue":{"value":{"entity-type":"item","numeric-id":3884147,"id":"Q3884147"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686299$C8E857B9-0792-4331-ABE1-4F9925DED803","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3d1eb3d868d04fb0bc6e3c75d517ea4c314251ae","datavalue":{"value":{"entity-type":"item","numeric-id":4712248,"id":"Q4712248"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686299$50C59DE3-8BCC-48EC-BB8F-39CA3A681D60","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1860b0031e2cbb9105661e4b1058c275782a39cf","datavalue":{"value":{"entity-type":"item","numeric-id":3135082,"id":"Q3135082"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686299$F51DF9FF-94EF-4B1F-A817-2130CFF34DAA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"156630a3a4c7b867c530c3fd60450b2705bd3402","datavalue":{"value":{"entity-type":"item","numeric-id":3963023,"id":"Q3963023"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686299$FA33137B-E5F1-49E0-A44E-D9D2A6995C6C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7a74f78e394da894fee17707b5a5f09c05559a27","datavalue":{"value":{"entity-type":"item","numeric-id":3745304,"id":"Q3745304"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686299$4DC9785C-D6B3-41D6-8737-A8743C0E482D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f1d2eb0918afb3cf49caac38c281af45e249ee40","datavalue":{"value":{"entity-type":"item","numeric-id":3873544,"id":"Q3873544"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686299$F96AC943-F4AF-4FB2-AC86-8119F179A823","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"94190943830c677a9dd172bfcc44b9dae50b0d1a","datavalue":{"value":{"entity-type":"item","numeric-id":3694715,"id":"Q3694715"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686299$E73D316E-9B1E-4508-B91B-31DB7C44987B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"62d035f421ab9bd8eaa29b517b29669cf50cb87e","datavalue":{"value":{"entity-type":"item","numeric-id":1144028,"id":"Q1144028"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686299$55DDB572-643D-4EE9-AA8B-521B97A663A4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"70bf83ac99b39c070945c45786ac4d3f9e43efdf","datavalue":{"value":{"entity-type":"item","numeric-id":1166531,"id":"Q1166531"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686299$533D4CCB-A878-4841-86F5-72F8D9DBC0B8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"babde1bf2e0a2ade6f34d07684713bf5358637f4","datavalue":{"value":{"entity-type":"item","numeric-id":3284374,"id":"Q3284374"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686299$CCEC44C8-8F9E-4FA9-AA9D-696C6BE9FFEA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"76d17cdc84d5a7c88fde84de7f32f71667e04184","datavalue":{"value":{"entity-type":"item","numeric-id":5470709,"id":"Q5470709"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686299$D495AFE9-76B4-42A0-8DDB-E3EEDDBCA8C5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"16ee6ba21410efd14ddd2a024a73c0ed4e5a2745","datavalue":{"value":{"entity-type":"item","numeric-id":4111952,"id":"Q4111952"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686299$1099E2EE-8AAA-45CB-AC8D-3BF470BD95A3","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"b1c626e6ea9d257074efbacb1a4da7807db183a0","datavalue":{"value":"https://doi.org/10.1016/0012-365x(92)90289-r","type":"string"},"datatype":"url"},"type":"statement","id":"Q686299$9DE9F5DE-CD70-40F9-817B-290418E46B21","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"7de9acd76a13f4e2e6133de26112005ff6086c7f","datavalue":{"value":"W2051679228","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q686299$E56D4321-0BF0-4353-A4F6-093B6F9055FE","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2e44e44c6dd7f1423034b84e0dab2b349a63c0b7","datavalue":{"value":{"entity-type":"item","numeric-id":5479033,"id":"Q5479033"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9a52bb7a390bef7adfbd49d140552042f788ce4b","datavalue":{"value":{"amount":"+0.8850722312927246","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":"Q686299$CC9C299F-D2E1-44B3-8A84-47002E2CCB93","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d6154c203b3ed09a9f444ef96d9a2f0c215d1079","datavalue":{"value":{"entity-type":"item","numeric-id":3447288,"id":"Q3447288"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"76841d22923e88826f26d681fa45aa39965a27a1","datavalue":{"value":{"amount":"+0.8442038297653198","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":"Q686299$60BD193B-0208-40FC-AF2A-FCCD97423837","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bc5c4e130e2f92d9bd3485ea2b5f548cfb71697d","datavalue":{"value":{"entity-type":"item","numeric-id":1362104,"id":"Q1362104"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"971d7a5b512d44451f2d634f8d8959ee41c06ee4","datavalue":{"value":{"amount":"+0.8415644764900208","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":"Q686299$3CFE8C4C-A4E8-4632-B4BA-0F84BE7B6414","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b2f3426688c7ee2c1ff5bcf51e69711db04fbfcf","datavalue":{"value":{"entity-type":"item","numeric-id":5479032,"id":"Q5479032"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"971d7a5b512d44451f2d634f8d8959ee41c06ee4","datavalue":{"value":{"amount":"+0.8415644764900208","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":"Q686299$9D8BFE05-0591-44B3-9066-36870E2D32C2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4efc42ed87593f2828937127842355ce8719d3f6","datavalue":{"value":{"entity-type":"item","numeric-id":4228207,"id":"Q4228207"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"04b0122ff1ae86602f28982bf88de9e846b58c37","datavalue":{"value":{"amount":"+0.8383366465568542","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":"Q686299$74CEF029-572B-4872-8EB2-C4C9A1104A73","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Tutte polynomials computable in polynomial time","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Tutte_polynomials_computable_in_polynomial_time"}}}}}