{"entities":{"Q3796747":{"pageid":5826653,"ns":120,"title":"Item:Q3796747","lastrevid":53221739,"modified":"2026-01-24T12:11:26Z","type":"item","id":"Q3796747","labels":{"en":{"language":"en","value":"A Natural NP-Complete Problem with a Nontrivial Lower Bound"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4062588"}},"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":"Q3796747$4CD40133-F084-4D83-A1AF-FF3ABE9786D1","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"298f99a073120d0559065f27d9672de2a58fc174","datavalue":{"value":{"text":"A Natural NP-Complete Problem with a Nontrivial Lower Bound","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q3796747$C078638D-43EA-4C15-8402-F1819BC18D16","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"889064d61da2b7bd836b1ba98c79072c48130888","datavalue":{"value":"0651.68053","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3796747$A42805BE-CA44-4160-A6C4-2AE81A7D516E","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"0ea42699a42b4e9b8cf9ff3c599d75d06780c170","datavalue":{"value":"10.1137/0217050","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3796747$00291113-9BAE-4011-85D2-7C2664149000","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"5dae8f46f54ddef78ce2c5c814dc33261ca054d1","datavalue":{"value":{"entity-type":"item","numeric-id":295629,"id":"Q295629"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3796747$05060BD7-A839-446B-9C3A-EC4E502433F3","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"c2a1c45d0f0997786c62faf9f7fcd603424632e8","datavalue":{"value":{"entity-type":"item","numeric-id":84798,"id":"Q84798"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3796747$8A991C9F-DC16-4531-8759-8FAE178220F4","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"31a1937240ca4a323604b4728c31d242b5596d7c","datavalue":{"value":{"time":"+1988-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":"Q3796747$8002E4B3-F733-4929-8C56-2A3E0A104B6F","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3796747$AB348830-75D3-40FE-9C2B-65D79F833A50","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d7656d1c841701431b0b3d99d23720089a267cbb","datavalue":{"value":"03D15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3796747$354656F0-EDA5-4E02-A0B4-BC219DAC5BED","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"200cb061b13c545ab6235342a9cd7719bbe03ce4","datavalue":{"value":"4062588","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3796747$4938E396-65D7-4D44-B543-B2985BE43786","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"da6c78b67096b558b6a5b7f77cad8eea1fc65662","datavalue":{"value":"linear time","type":"string"},"datatype":"string"},"type":"statement","id":"Q3796747$1036EBF6-B651-473B-96D4-0C33930F9C97","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0e0192fb524376f45dfdd3eb1a809bf3cd5a9489","datavalue":{"value":"lower bounds","type":"string"},"datatype":"string"},"type":"statement","id":"Q3796747$8FE7E139-EA44-47E6-B06C-764EC4E0BF00","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1c8c9e80036612c21ad2ec3b6579e3228fd2ea1e","datavalue":{"value":"NP-complete problems","type":"string"},"datatype":"string"},"type":"statement","id":"Q3796747$7DAF89D2-0596-4009-827D-17422701CEDB","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":"Q3796747$833740A3-7715-47A3-AD9F-6D8024D4FCC0","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"481761ddd2a50c9a5791f5a71dee107bb115f30f","datavalue":{"value":"https://doi.org/10.1137/0217050","type":"string"},"datatype":"url"},"type":"statement","id":"Q3796747$96663709-8D40-48A9-9199-2D7424CCB7BE","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"5726d8fe00f9dd80dfee6f0e0eabda3c2c988944","datavalue":{"value":"W2057894153","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3796747$03BA3F8B-D880-4F8C-8664-E83F43B92F61","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bcf4e0fa6fbfb6f1de34315c6d7a1e5527319c63","datavalue":{"value":{"entity-type":"item","numeric-id":3455999,"id":"Q3455999"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2d2aa3b0c83cb0b784133624075f2eccbc9096b5","datavalue":{"value":{"amount":"+0.8790905","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q3796747$5B6FB49D-4C94-4717-91E3-95C764D6D335","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"24ec9455f54c32283ad7953bf6c8ed6237e5816a","datavalue":{"value":{"entity-type":"item","numeric-id":790612,"id":"Q790612"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e9bb35dce53dd83b7d2bc06cc5914987eb80fc9f","datavalue":{"value":{"amount":"+0.87708807","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q3796747$080AB7DD-549D-49A1-A37B-BB0216821ECC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5bf38cc888921590df143be54d6b97aac5f0ba8c","datavalue":{"value":{"entity-type":"item","numeric-id":4668733,"id":"Q4668733"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"817b59bd0bcd365d862a0e9ac7117efaee2177a8","datavalue":{"value":{"amount":"+0.8754723","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q3796747$BE622774-5AE1-44DC-BBED-0F4EEB66E4A3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d02627a07279b5f9f272a3ef591f830eca364c33","datavalue":{"value":{"entity-type":"item","numeric-id":4279733,"id":"Q4279733"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a4985776085407282e509ad6eda10208c2e3362f","datavalue":{"value":{"amount":"+0.87182903","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q3796747$6E56CA4F-591E-4D58-A11E-1FA70F7C30BB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a267ec6f39e378d62256d037e0e191fa163141e2","datavalue":{"value":{"entity-type":"item","numeric-id":3477958,"id":"Q3477958"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"495fa7f8bdf2fe37c52e24029b88f9f9fcc75b67","datavalue":{"value":{"amount":"+0.86707675","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q3796747$F749BB59-6CB5-4C42-92D2-506E3137AAD5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1bdf783b34ecf6b1582322be95f8030f91c659fc","datavalue":{"value":{"entity-type":"item","numeric-id":626691,"id":"Q626691"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ec8b50d58869568403d2b289ab7ade932a70fbae","datavalue":{"value":{"amount":"+0.8669034","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q3796747$C3D07EE0-9788-472A-AF1A-0F2F29595E98","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e4798a608c6785aed8b6aab66fb543734ca522fa","datavalue":{"value":{"entity-type":"item","numeric-id":1903594,"id":"Q1903594"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f55c02e44cf98fb1470a02f69933c1101b379afd","datavalue":{"value":{"amount":"+0.866122","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q3796747$FDC6FF5C-0CFD-42AE-856C-158AE370D196","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3714a9bbca0c040b70169a5deacb598ad06e46f3","datavalue":{"value":{"entity-type":"item","numeric-id":5309712,"id":"Q5309712"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"82e699509b085e2e2b509bad4e678072b386ff90","datavalue":{"value":{"amount":"+0.86411417","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q3796747$9AAD5115-2610-43B6-B2CA-CD8048DADE5B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8e5d08da4ebcf5bf8f79e8e4b9dc61d7f8468a2b","datavalue":{"value":{"entity-type":"item","numeric-id":3340499,"id":"Q3340499"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"65d55f1643f6081d574e26e5245f3e970abfa987","datavalue":{"value":{"amount":"+0.86402726","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q3796747$53E344AC-A6CD-4EBC-897D-DE2EB33855B3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"638d1de8931721755fd74add0cfdb274275611ae","datavalue":{"value":{"entity-type":"item","numeric-id":5402559,"id":"Q5402559"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0a355eac78cc686c0f19aad9061021585315ad69","datavalue":{"value":{"amount":"+0.86090153","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q3796747$E3464222-C064-468A-A1CF-9F47C4B7AB02","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:3796747","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:3796747"}}}}}