{"entities":{"Q343929":{"pageid":345696,"ns":120,"title":"Item:Q343929","lastrevid":61161039,"modified":"2026-04-10T21:33:42Z","type":"item","id":"Q343929","labels":{"en":{"language":"en","value":"DAG-width is PSPACE-complete"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6657249"}},"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":"Q343929$F2D575E6-79F5-4C84-A7C4-6FE28A54B2DA","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"813d7ea8fc5b5c4264375d5fe37a8c57ca017d9e","datavalue":{"value":{"text":"DAG-width is PSPACE-complete","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q343929$7334E0B3-D040-4334-BC54-3EE76A93D9E2","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"667289d76b4c2c7bb9e2b8014c8c33a583678095","datavalue":{"value":"1353.68105","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q343929$4E05375E-2C18-455C-BC6A-1209264020D6","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"3012cca9b6c96fddcc2c4ab21696582d2b829123","datavalue":{"value":{"entity-type":"item","numeric-id":343928,"id":"Q343928"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q343929$2C946492-087B-450E-9BF8-0C5FCCFA62A9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d5e3d022de394d7241ddffa43602fc112cf57e9e","datavalue":{"value":{"entity-type":"item","numeric-id":266261,"id":"Q266261"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q343929$0195A4F1-FA65-4BA8-8EEE-6C4E969D4DFF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"9a33341797c860a0bd34732ecf0f1304fd0e9d1f","datavalue":{"value":{"entity-type":"item","numeric-id":322314,"id":"Q322314"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q343929$82C4B24C-E4BD-4561-B3E2-42D080CAE3A6","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f3c424cd94a60f9664f9fb69cc6027e75cc7ff3f","datavalue":{"value":{"entity-type":"item","numeric-id":123643,"id":"Q123643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q343929$5B6E51C3-C86D-450E-8519-7EFB77B6B7AC","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"9006bedee625b95dd1298ec43d8a3c4ce5359c84","datavalue":{"value":{"time":"+2016-11-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":"Q343929$BB0F0FE1-D061-4DC9-AE56-6A3BFC8A1A8A","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"e62b8fc2d630f2e58845dab62726305418039f92","datavalue":{"value":"https://arxiv.org/abs/1411.2438","type":"string"},"datatype":"url"},"type":"statement","id":"Q343929$641F552A-B5F8-46AB-B254-083B762CE26D","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q343929$5352053A-3372-4FEA-89D0-F4B3814E62C0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q343929$5CD19874-1691-4FA8-AF4A-205B422E38AA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"2fd5ba61c492f09082ae88370fa92e256be14e94","datavalue":{"value":"05C75","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q343929$3EEDFA29-AF9D-4822-AF44-F7AD36DA2C7E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q343929$3EFC7AF2-99BF-4923-969B-71C5E5DAA936","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q343929$513F8679-E8CF-43A4-BE10-10359713F076","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"14802ff25838de0c7521f0e3e0141d2a01b04487","datavalue":{"value":"6657249","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q343929$838F22C3-0DB3-4269-BA69-8D0AE27C96CD","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"40310312ea8617d10fd7a71af56f76f046dd5a1b","datavalue":{"value":"graph searching games","type":"string"},"datatype":"string"},"type":"statement","id":"Q343929$9FB6E0F6-CBEA-4DF7-BE2B-B6DA9A4F61A3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9b38360a549dda68170111597affa53fc65c4a00","datavalue":{"value":"DAG-width","type":"string"},"datatype":"string"},"type":"statement","id":"Q343929$4DB48B1B-E58B-4BFE-AFFC-E339ECDB47B0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a05cfd9da536bc8387292ab9359d3f7e9902a360","datavalue":{"value":"PSPACE-complete","type":"string"},"datatype":"string"},"type":"statement","id":"Q343929$2940D714-AEF1-402C-B2B9-6A7AE92F19BA","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":"Q343929$4CE59F01-C34B-4439-8B2B-24C30B880911","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"602f6776c27297656688a8ed5ea795fd7f547368","datavalue":{"value":"W2964025853","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q343929$1715B067-AD70-43DB-B404-4077258C31BF","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"d0f939a8eeb311294398102533d19360884f36b0","datavalue":{"value":{"entity-type":"item","numeric-id":2502026,"id":"Q2502026"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q343929$DE2A1E2F-F1DB-4055-BA43-930EED8E2E1F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"832a7ad41572172e5555bf91ea79aa1e789ef798","datavalue":{"value":{"entity-type":"item","numeric-id":444380,"id":"Q444380"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q343929$B5ABE51C-5EF9-416A-984D-472795BF0D4A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6d49ebb0717c0913503c5d78bad700eaa23bc958","datavalue":{"value":{"entity-type":"item","numeric-id":3075456,"id":"Q3075456"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q343929$450709CF-2B0C-492C-8728-48618F0FCC10","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1215c8751c540d1e87f1a3d414463ad3c2f088dd","datavalue":{"value":{"entity-type":"item","numeric-id":1811076,"id":"Q1811076"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q343929$3E7FB112-D60B-4BC0-A8D9-5CA197448F66","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":"Q343929$BF3753FD-4F9D-44C8-ADCA-54ABE714B47E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"167507a49c8cbea5342ed0259ac705047224f9a0","datavalue":{"value":{"entity-type":"item","numeric-id":930893,"id":"Q930893"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q343929$723D2B4D-F3B7-451E-85D4-26B0058962DB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"12600cb24649ba9815ffcfab5b752a2fd38d0d39","datavalue":{"value":{"entity-type":"item","numeric-id":1850539,"id":"Q1850539"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q343929$E351276D-0781-4C9F-A700-C48DEF84DC25","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"29e4165802b472a53ee5a415cf6dfae9c72cb86f","datavalue":{"value":{"entity-type":"item","numeric-id":5851115,"id":"Q5851115"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q343929$D64ECE24-F9E5-4908-A9D3-637C77668171","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a539afe62212faa649f3b77fb132ca8fd10ad1c7","datavalue":{"value":{"entity-type":"item","numeric-id":2741376,"id":"Q2741376"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q343929$36C3624E-AE16-4191-8A6C-C1091697566B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6dc5ea010dc9e66cca0468ff9a85e52ca33f6b25","datavalue":{"value":{"entity-type":"item","numeric-id":5492905,"id":"Q5492905"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q343929$12283E82-759D-4868-B27F-8A164271FD02","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"4ba2c0ca8f5d12cd6d892f63931cf67bf8be28bf","datavalue":{"value":"10.1016/J.TCS.2016.09.011","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q343929$DE7EEA97-350E-40D0-BFB2-8AAABF7D0C19","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a9de9f94c89d5331468f97d553be946f3b338e5b","datavalue":{"value":{"entity-type":"item","numeric-id":444380,"id":"Q444380"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"07a97109a59783b03d8c9b048e49c43994dc56cf","datavalue":{"value":{"amount":"+0.8337157964706421","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":"Q343929$E16DBF99-7F53-4D41-9B96-864DDD973FD1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"88a4ad42b35211948c6225675b19879b60e2dfae","datavalue":{"value":{"entity-type":"item","numeric-id":5449827,"id":"Q5449827"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4a0486ecac2bb73a63d855b165bf202d650c466f","datavalue":{"value":{"amount":"+0.8304786682128906","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":"Q343929$794AF812-038A-4BF2-8AA5-2FDE2A19A9C6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"80d0686056fb98f5547c57220899977f6831b5d4","datavalue":{"value":{"entity-type":"item","numeric-id":2954982,"id":"Q2954982"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c5509e19fbf098f2ae066a76ab786a9320f7ebfe","datavalue":{"value":{"amount":"+0.7468207478523254","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":"Q343929$1612FEAE-A6A1-46B4-A69D-99B82A4F6141","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"96778d953938e46d987801b228566d9da843ff0e","datavalue":{"value":{"entity-type":"item","numeric-id":2811203,"id":"Q2811203"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3469cf42a669fb53d6ea8f600eb3ecd7bef6c252","datavalue":{"value":{"amount":"+0.7319062352180481","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":"Q343929$D00CAD21-3577-4076-9F17-4CB83DD63E84","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1753c69240591057d1861df69b0d4300813e33ce","datavalue":{"value":{"entity-type":"item","numeric-id":2442211,"id":"Q2442211"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"94ee2da1ac91c8b0603e8f3900f69d429753a30d","datavalue":{"value":{"amount":"+0.7303993105888367","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":"Q343929$64CC60A5-D7A1-459F-9560-10D6B9C37C1A","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"DAG-width is PSPACE-complete","badges":[]}}}}}