{"entities":{"Q1019749":{"pageid":1021597,"ns":120,"title":"Item:Q1019749","lastrevid":50665313,"modified":"2026-01-14T17:51:29Z","type":"item","id":"Q1019749","labels":{"en":{"language":"en","value":"Finding a tree structure in a resolution proof is NP-complete"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5559010"}},"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":"Q1019749$DF3F35C7-8F4F-4D83-8C91-1E6AAA9261FF","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"90477baf3a83ec705fe3f4c5e1efa2a6b2a22b47","datavalue":{"value":{"text":"Finding a tree structure in a resolution proof is NP-complete","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1019749$3CE83D68-EF7E-445C-925F-DBCC82CFC932","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"58fa4f36ee93eaa5f2bb2d2ceee45c0e1b807e5d","datavalue":{"value":"1166.68038","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1019749$24131913-9B9B-409F-A16F-5A30988FD8D3","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"e88be69c40b517dcf95562e728bf82dd0b4372ca","datavalue":{"value":{"entity-type":"item","numeric-id":372958,"id":"Q372958"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1019749$6913E279-1A93-4BF2-895B-C66314D93EB1","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":"Q1019749$723AFDD5-7532-4DF0-A189-CA459B5A1C80","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"007d554cae8390924a30c1fbbc213e981500b382","datavalue":{"value":{"time":"+2009-05-28T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1019749$C0525AE5-37F0-4DFF-8BE8-04B97E98A86C","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"e6e7c2e9d67f9590a26e18c734f34db53ce5ec87","datavalue":{"value":"68T15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1019749$4067DDA0-AB95-44E5-8F84-55557F222B06","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"10eaeaf8bbf8231bbfc812aab8956e260b5a9f12","datavalue":{"value":"03B35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1019749$9469F55D-C718-4B9B-8E41-10C765123A1A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6e2ae8b1900147d15ddea62ccb5302a15ee19b5d","datavalue":{"value":"03F07","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1019749$43648DBC-8BB3-41C9-9839-99045AC2654B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1019749$3F6CC9F6-0EB6-45DA-BE9F-DDF0DA9673B7","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"e088219930beae080aee1cd0670d4334ebd4063e","datavalue":{"value":"5559010","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1019749$FB079F4B-0E09-4DCC-B2E2-0FE9E74142B7","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cfac5eb6431ec88e2a6e9bafbfcf7b49dda794fc","datavalue":{"value":"resolution","type":"string"},"datatype":"string"},"type":"statement","id":"Q1019749$34AFA8C8-2C08-4F11-96A5-9B716E24E2D1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"eae4596ec247ace64446caee7b381f3e737abbe7","datavalue":{"value":"tree-like resolution","type":"string"},"datatype":"string"},"type":"statement","id":"Q1019749$F53AECDE-BAC9-4C03-B9D6-E4BDD55CC183","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cf1bbad404b660dcc4f7e1f74269a25b269f6b2f","datavalue":{"value":"NP-completeness","type":"string"},"datatype":"string"},"type":"statement","id":"Q1019749$603D6DDF-3CEA-410B-957B-EF3037BDF458","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":"Q1019749$2D564362-3728-4CCE-BA99-CCEF3A2CB0B2","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"abf46dfc4d816bdb8100bb84ae0704b9207b5ad3","datavalue":{"value":"https://doi.org/10.1016/j.tcs.2009.02.018","type":"string"},"datatype":"url"},"type":"statement","id":"Q1019749$300F3ADE-5CEE-4228-8ABA-A00BF8E67886","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"42d3b94b8c160c46b200ac7c76ef543cb80d9e22","datavalue":{"value":"W2032927579","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1019749$12DEA0AD-FC84-46E2-9F35-98110839E957","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"f9cb2a4e4fb6a095d91ee24830284f50b193c2fb","datavalue":{"value":{"entity-type":"item","numeric-id":2732273,"id":"Q2732273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1019749$9C52573E-5C16-4CB8-80FE-23134CA18C03","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"25eb460d58931676e51733807df783912964924b","datavalue":{"value":{"entity-type":"item","numeric-id":3002781,"id":"Q3002781"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1019749$B23F46B9-7AC7-4A59-9F02-A6188FAB7840","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"088d50352df9ad001d77073382165c77d3798fad","datavalue":{"value":{"entity-type":"item","numeric-id":3395034,"id":"Q3395034"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1019749$1EC99884-9DC7-4462-B875-1AA7CBA260B6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"25cd1afd6809f2236d203cad789f950bef0e99a8","datavalue":{"value":{"entity-type":"item","numeric-id":558312,"id":"Q558312"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1019749$454D9B07-4CED-4E20-BE25-E6A417E0E9D0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"08b529296035947435eb136154e374f9657d895b","datavalue":{"value":{"entity-type":"item","numeric-id":4406287,"id":"Q4406287"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1019749$B76A2009-B4AE-45EA-A5DB-F15BC840A699","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"712ab9879533678bd2c9a87309dbe10aa68db58b","datavalue":{"value":{"entity-type":"item","numeric-id":924157,"id":"Q924157"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1019749$42C8F743-1741-42DA-9BCF-B07DECAC3D38","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ae8e8c7e4d2f66af1d6d76f2c025c2520cd9b217","datavalue":{"value":{"entity-type":"item","numeric-id":3623009,"id":"Q3623009"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1019749$561902D6-AC89-44D9-8C86-A9407B4E3F0A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0bea75da9fa67a5f77faa9362cd4aa6c737c792a","datavalue":{"value":{"entity-type":"item","numeric-id":4194955,"id":"Q4194955"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1019749$3D2235E5-154A-4220-B497-360EF7D8D7E1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ec2fa04d400281f100817ce7e13bdaafd2683670","datavalue":{"value":{"entity-type":"item","numeric-id":1071750,"id":"Q1071750"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1019749$F1FB388E-61E8-400B-A573-C5ECCA0D42EA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2d00577aaab877471eab13639deaf5bae1c0a78e","datavalue":{"value":{"entity-type":"item","numeric-id":4699307,"id":"Q4699307"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1019749$CDECAA70-99AE-4333-A16F-3A46EF8E0196","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"847f43a12784abd824ccccc602688df087916fcc","datavalue":{"value":{"entity-type":"item","numeric-id":3565237,"id":"Q3565237"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1019749$CFC0D21B-A128-4BBD-8034-B3DCCDBA33FF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e98bea2faf0f1e7139247049b725eb54de257627","datavalue":{"value":{"entity-type":"item","numeric-id":5593816,"id":"Q5593816"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1019749$E2D9563E-C2FD-4595-A47A-0F8F1D59A905","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"fe0028f8b2a0c2c81248f2c1b54bf9415f5e7037","datavalue":{"value":"10.1016/J.TCS.2009.02.018","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1019749$AFE9F210-05E4-4135-BAF9-4197FA5ABEB7","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c5f4394b21684c04002ff736e5ad3cfbd02aad32","datavalue":{"value":{"entity-type":"item","numeric-id":924157,"id":"Q924157"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e47ca15836d5ea1a1ca0ff676cb96ff0f50c30b9","datavalue":{"value":{"amount":"+0.799350380897522","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":"Q1019749$97D1B001-652F-4B92-8FD8-5ACCCD27521D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e38c5eda6b1781bc7d63173524f756d4e3ddb84c","datavalue":{"value":{"entity-type":"item","numeric-id":1042441,"id":"Q1042441"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5fefc563e6aef1e93afd0d1ae9e63705a4152afb","datavalue":{"value":{"amount":"+0.7937756776809692","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":"Q1019749$8253A78D-75B2-4433-A2C3-E07762E03F59","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6559d5ee1ba8e39e66a21398b6a8e72552188532","datavalue":{"value":{"entity-type":"item","numeric-id":1601038,"id":"Q1601038"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cb4ace3979b9da046a31c956c7aaf7229110a339","datavalue":{"value":{"amount":"+0.786178469657898","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":"Q1019749$8FA18806-942D-48B5-ADA1-26BDBE4BDBF4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"df55a45de7dff4311abedd1f8ac3eacd8d1df8be","datavalue":{"value":{"entity-type":"item","numeric-id":3343454,"id":"Q3343454"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cb4ace3979b9da046a31c956c7aaf7229110a339","datavalue":{"value":{"amount":"+0.786178469657898","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":"Q1019749$D60C1A17-3A38-4987-ACC6-F2C944E2CAC6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6bab55daa23f01302987ce4dbcd938d0bcf89500","datavalue":{"value":{"entity-type":"item","numeric-id":5133983,"id":"Q5133983"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a4dbc7889fae91546e5c16d1bd8f3537b8b27640","datavalue":{"value":{"amount":"+0.7795844674110413","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":"Q1019749$7B5011F9-E3E7-4DB8-8593-105F1968437F","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1019749","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1019749"}}}}}