{"entities":{"Q3747723":{"pageid":5777629,"ns":120,"title":"Item:Q3747723","lastrevid":51007706,"modified":"2026-01-16T04:44:25Z","type":"item","id":"Q3747723","labels":{"en":{"language":"en","value":"The NP-completeness column: an ongoing guide"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3984570"}},"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":"Q3747723$E1464A6D-0454-4440-BA99-EFCC7CDF2055","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"f8ede124584209def58e4946720d9aadb4a0d081","datavalue":{"value":{"text":"The NP-completeness column: an ongoing guide","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q3747723$375C4104-0CED-439A-9D94-6901F6A23C41","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"504d92de41127f48340dab5c04e91ac90dbe606c","datavalue":{"value":"0608.68032","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3747723$FC4D2311-C047-4D47-881A-2F78D97066ED","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"53fbd3fea06fb222c43b0a7f537c79a58005f7b4","datavalue":{"value":"10.1016/0196-6774(85)90012-4","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3747723$D394DB83-D412-4A86-B6D6-4DDF4E11EFFB","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"9bcfebe9d23b7752651008b0d843e08ec7c57a37","datavalue":{"value":{"entity-type":"item","numeric-id":2709787,"id":"Q2709787"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3747723$DAC51508-92FA-48CA-B6CC-1A1E4F4B8209","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3c94df5c9af0ede578c52141befd29044de13172","datavalue":{"value":{"time":"+1985-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":"Q3747723$D8AA51A3-0C7E-4CB9-B8E2-F3B3D5CDAD4D","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3747723$B157A82A-F63D-4CE3-9DB5-16332C2349C2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3747723$EE102C95-3194-468B-A473-40AEA6791B93","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"945c2ef2e73141eba40e7b39868e4336d82a1acd","datavalue":{"value":"3984570","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3747723$25E735E1-4AA7-4AC3-AD97-16FA112151CE","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c7d5e4886aa4290eca104cd0d1da319d8b4d34c4","datavalue":{"value":"NP-hardness","type":"string"},"datatype":"string"},"type":"statement","id":"Q3747723$AE031F24-D702-422E-92E3-6215F208A04C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f590d7d5a7bf2c06d3ed026c82bb5f77bb5f23f2","datavalue":{"value":"near-trees","type":"string"},"datatype":"string"},"type":"statement","id":"Q3747723$3C30535A-9090-4AFF-B5C5-4F50A195C3C9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c856145ef6cf7ef96d1f0755055e2ec6f5396f57","datavalue":{"value":"planarity","type":"string"},"datatype":"string"},"type":"statement","id":"Q3747723$8435D172-6628-4907-9143-23299BC586DB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ad953c972dffaf55600680cb93d5c1f4085c4b91","datavalue":{"value":"perfect graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q3747723$A3A15449-73B8-4C33-B9C0-DE60B6B189B6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"25f8eba8c9d529f212c848e074f37e4d66acf3cf","datavalue":{"value":"intersection graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q3747723$4510BD9C-83B3-4F8B-8EA4-B75BC458B2BF","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"a2d2e9e9928a5f0aeb67e9d8dc491adf69b67d3c","datavalue":{"value":"Q29038371","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3747723$45ED1DD2-12EC-4758-935C-E2201EB818DD","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"ecf2d8824396c280beb38bdd66733991f0508cba","datavalue":{"value":{"entity-type":"item","numeric-id":721935,"id":"Q721935"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3747723$F0D17325-2CA8-4BD0-AD3C-03E6107278DC","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":"Q3747723$989E220B-FC5B-4D2B-BE41-2675C7B31A9D","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"3dbf819e1da2f9fb77fb600c880617da1902bf13","datavalue":{"value":"https://doi.org/10.1016/0196-6774(85)90012-4","type":"string"},"datatype":"url"},"type":"statement","id":"Q3747723$C6953C2B-85F8-45C7-BE4B-C64F43D2E92F","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"9da10a2fd76affb6367d0dfe3a4ec954af1e53be","datavalue":{"value":"W4361867857","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3747723$BAE86138-60EC-4C74-ACC7-A0BD1A887C0B","rank":"normal"}],"P1635":[{"mainsnak":{"snaktype":"value","property":"P1635","hash":"36efeb6f6886720e796008b9d47dd23fd7eaca16","datavalue":{"value":"journals/jal/Johnson85b","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3747723$18C80E12-411D-4032-AB50-AB621FB28F49","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"07eb33418e8fd8794a505ce714b1f2aca15488d1","datavalue":{"value":{"entity-type":"item","numeric-id":5896449,"id":"Q5896449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"df108e728de1f3704b744d9377c1f35bbfa4791c","datavalue":{"value":{"amount":"+0.9784711","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":"Q3747723$0E183001-FF2E-4080-AC4F-C89325E1492B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d27bffa370c1f1921755c8c0acb519a2d6fa102d","datavalue":{"value":{"entity-type":"item","numeric-id":5896419,"id":"Q5896419"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6a46362b3931c32635c492d9c28c99d732531953","datavalue":{"value":{"amount":"+0.9772712","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":"Q3747723$A582E86D-5A07-4DFD-BB31-ED70D4FC2F60","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"68193b8ff634e09f0c368c565296d2b259316829","datavalue":{"value":{"entity-type":"item","numeric-id":5902702,"id":"Q5902702"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"99bd4b443e330256c7c5f2db368178ab23de8746","datavalue":{"value":{"amount":"+0.9767294","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":"Q3747723$C6C62F35-90AD-4DF4-81A4-25D513A46E91","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"337dbd5fc4aa7d498dc1079157d7b6d1f14890cf","datavalue":{"value":{"entity-type":"item","numeric-id":5902703,"id":"Q5902703"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ee5395814f9d11abd0a0b5027327eb922f62effc","datavalue":{"value":{"amount":"+0.97613657","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":"Q3747723$43509CC0-A904-4D18-B42F-3A7DABF9F5CF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b15e26fbe9ee22618c3ef7b604ec7c9b88452cc4","datavalue":{"value":{"entity-type":"item","numeric-id":5893777,"id":"Q5893777"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7904d2419bd1f571cf61e25cb8ae884466e39387","datavalue":{"value":{"amount":"+0.97561246","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":"Q3747723$47341A3D-D84C-4FE6-8C6E-AD602A73C846","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0630e24f0aadce3cb4b9548bdaf447f4161ade0d","datavalue":{"value":{"entity-type":"item","numeric-id":5903311,"id":"Q5903311"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"577eee8bc5ca24f71d9e7480fbbe19a43604e806","datavalue":{"value":{"amount":"+0.9745457","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":"Q3747723$E96E9DC0-2A1E-4E9F-9545-66EB8E4C12D0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"64b81b1565a66bfcd8449d2f95131bcc9630136e","datavalue":{"value":{"entity-type":"item","numeric-id":5903717,"id":"Q5903717"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"66f936a029d85c67b376cc86991782c4149c26ac","datavalue":{"value":{"amount":"+0.9737222","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":"Q3747723$2A11CBC1-3951-408B-AC47-824C8130AC5A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4ded959e5d9ebdb4b5fab9515153d4ed509ba5df","datavalue":{"value":{"entity-type":"item","numeric-id":5903516,"id":"Q5903516"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6662b2c70070e39092f781921731c2ac70e05bb5","datavalue":{"value":{"amount":"+0.97258437","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":"Q3747723$8E42F795-DD6F-448A-9D67-716EF15D268D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"37f10de424d06392072dc58fc7d40a3023f10eb9","datavalue":{"value":{"entity-type":"item","numeric-id":5966695,"id":"Q5966695"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4bbfeac1fe91e9f7da4ad3f07f9dd58a68b38df6","datavalue":{"value":{"amount":"+0.9715936","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":"Q3747723$2A761943-752F-4F40-8146-E9DD613BC90C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cf79f4e7096275781b450568e680f7a10c89c935","datavalue":{"value":{"entity-type":"item","numeric-id":5896404,"id":"Q5896404"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"af3d2eea51f25c323c12f583cdf707f38ca1c61c","datavalue":{"value":{"amount":"+0.9662674","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":"Q3747723$88D0CE04-6D54-4319-856E-6CC13DE00593","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:3747723","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:3747723"}}}}}