{"entities":{"Q918697":{"pageid":920545,"ns":120,"title":"Item:Q918697","lastrevid":65378280,"modified":"2026-04-12T02:11:09Z","type":"item","id":"Q918697","labels":{"en":{"language":"en","value":"Recognizing tough graphs is NP-hard"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4160130"}},"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":"Q918697$8E2D2BE6-128C-4404-975C-5FFA3EC10929","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"e4c59ce27b45effbae7bcf1d9d402d83daa26995","datavalue":{"value":{"text":"Recognizing tough graphs is NP-hard","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q918697$D1E05B0C-8F37-4DA2-A973-DBE71F125672","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"76ad675b792bf9f3d841713b61d9e7305abb8359","datavalue":{"value":"0706.68052","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q918697$26162A2E-E667-46AD-9F4C-00116B6829BF","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"20557308f2b8505a952679c0f366b73eca89e113","datavalue":{"value":"10.1016/0166-218X(90)90001-S","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q918697$719C53DA-C7F3-48C7-BC38-0EB7982EC717","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"087f55844cc920aae060b09644168bf17b022e1a","datavalue":{"value":{"entity-type":"item","numeric-id":96294,"id":"Q96294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q918697$677A5D00-0E90-4AC4-B2ED-2361A265A8BD","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"70d2fbf8bcd48a5ca1ac752985098b379d0dbb65","datavalue":{"value":{"time":"+1990-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":"Q918697$2C573CD4-C848-4DBE-A693-5A20B36D4DEB","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q918697$E033A047-2037-4A5B-AF76-508B6ACD4617","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q918697$A14316A8-5AA8-4F83-A4F6-54B2B2B23B67","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"eef1b49f4a66afb755b22d7419db9d61ba07415f","datavalue":{"value":"05C45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q918697$DE0CE5FD-96BB-4DEE-A0AE-CB924EEC1811","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"3b9c14ce3ada92d220dec9675070fac8bcc7d109","datavalue":{"value":"4160130","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q918697$84DD2EE4-FD2D-4782-B1CC-9E1162AC544C","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b1876f477d72d21c2eb9b3a47fe0585b932ab3f7","datavalue":{"value":"tough graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q918697$CD05BB5F-0176-4C17-860E-77C8DB523F28","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"5c89625df13d44fcd5d80c2c4da74816944be33c","datavalue":{"value":"Q61248964","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q918697$94C89BD4-59CB-40E6-8E37-3785FA90D69A","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"60ae56b79890118017fdfa61d163ccabbb05d00b","datavalue":{"value":{"entity-type":"item","numeric-id":585220,"id":"Q585220"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q918697$49484095-C618-42F5-824C-86A6D04B41AF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"689d64a7dc4667e6ec215ea2a9161abc905c1a0e","datavalue":{"value":{"entity-type":"item","numeric-id":290245,"id":"Q290245"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q918697$9D9CB64F-D6DD-4132-8D85-981F0A42241D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"41fca74e9950a16c663ca86f884e7b8febbc1dc4","datavalue":{"value":{"entity-type":"item","numeric-id":290246,"id":"Q290246"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q918697$14C530B3-A964-422D-AA6A-CC3D69757D3F","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":"Q918697$67F1B7B9-90ED-425B-ACA5-487352EE5EB8","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"f7b6f9b4f824c6e8cbb9f7dc37ead7fa403bd8c9","datavalue":{"value":{"entity-type":"item","numeric-id":749553,"id":"Q749553"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q918697$A0D18CC2-A9F4-4616-B922-DB0A4368A533","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"559dbe579a3334aacf82df2fdcef598c181017c4","datavalue":{"value":{"entity-type":"item","numeric-id":5422499,"id":"Q5422499"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q918697$621CB87A-AA62-483A-9C1F-857E5138CC51","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4a2ca07d50aa240b4ccbe9fedf2b4516f9bba12f","datavalue":{"value":{"entity-type":"item","numeric-id":2558871,"id":"Q2558871"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q918697$C7EC6D31-9B14-4CA7-A85C-C59679D5F5D3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"79b2cd01bd8642a86b4a476512521b17956a3210","datavalue":{"value":{"entity-type":"item","numeric-id":3689218,"id":"Q3689218"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q918697$073FD0F5-6127-4302-9323-854068C55119","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8788f05ae82cfbd0ae01fb3681f4ca02a719c218","datavalue":{"value":{"entity-type":"item","numeric-id":3731636,"id":"Q3731636"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q918697$26548E0C-4FA9-4687-BD34-DA1157D41A3C","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":"Q918697$A271C2B0-CDD9-43F4-AE1C-91BC85538171","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bd1e88ea96020b3b4e0875e21b4861205a511d18","datavalue":{"value":{"entity-type":"item","numeric-id":4182545,"id":"Q4182545"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q918697$1D8F6DCD-DBE2-4FCE-98EB-0D683089DC36","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"36ee50751423e7be45099eb78259a74d9e4a0dc9","datavalue":{"value":{"entity-type":"item","numeric-id":3901539,"id":"Q3901539"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q918697$4B9EA9EC-B04A-4CEB-9E49-4DD60EAE4F98","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"b9f9b66d4f55e070cd81a7f335f9a21af89708ed","datavalue":{"value":"https://doi.org/10.1016/0166-218x(90)90001-s","type":"string"},"datatype":"url"},"type":"statement","id":"Q918697$AB9E89B5-8B92-47E6-B5FF-6F44B6B1512C","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"1e9cb4f6b49b81a385d54fe8edb1553dbed8efc6","datavalue":{"value":"W1981583245","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q918697$21604B38-7C9E-4325-8B41-1E1849B5E26F","rank":"normal"}],"P1635":[{"mainsnak":{"snaktype":"value","property":"P1635","hash":"570b6190e4c2ded7fbd2d0896bb43731b1b7bf4b","datavalue":{"value":"journals/dam/BauerHS90","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q918697$977758DB-F489-494B-835C-877453E3A81E","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c80c4fcf5b116a614d0539301548150a54dcef92","datavalue":{"value":{"entity-type":"item","numeric-id":1313820,"id":"Q1313820"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cc97cbe6ad4737787f25992ec3cb5b6fbd1ad247","datavalue":{"value":{"amount":"+0.95340884","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":"Q918697$DC12181F-8E90-4CC5-A302-05BD427592E1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"acb63bd32da9bd4849787d0a5795482b3559d8f4","datavalue":{"value":{"entity-type":"item","numeric-id":5502385,"id":"Q5502385"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f85894987063253c8ced0624aa7900345b205722","datavalue":{"value":{"amount":"+0.9238191","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":"Q918697$5053ECF5-0CEE-4474-B086-09D4A516A25D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"32ccaa445a0d34d9229c21ba0768622187077068","datavalue":{"value":{"entity-type":"item","numeric-id":2656956,"id":"Q2656956"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9df7870d3a3161efbe3b9c29dfe0695b30d4888d","datavalue":{"value":{"amount":"+0.90609443","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":"Q918697$ED085C9A-2ABF-4711-BC2C-6BB2843057D0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2a2a4f5eeda92c8acfa0dc9362410ca3b02a1f2f","datavalue":{"value":{"entity-type":"item","numeric-id":839773,"id":"Q839773"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"eb4cbb03d45c520040f10df9459e725f248d23b3","datavalue":{"value":{"amount":"+0.897601","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":"Q918697$63058900-7AF9-44DB-A5E7-65834022AE7C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4244cd6f6169027847624a0596162fe9dbabd1da","datavalue":{"value":{"entity-type":"item","numeric-id":760213,"id":"Q760213"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f38ab2315c42627fec9ee4a1fc231f69c00eb262","datavalue":{"value":{"amount":"+0.8899978","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":"Q918697$1C0D4FAA-6994-4D54-8753-3D0AC48D15B4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"83ff962a20855c18d17049e581f9f63a24328662","datavalue":{"value":{"entity-type":"item","numeric-id":1372728,"id":"Q1372728"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fd9215ed49de8113bc6a20240b32843d7e105b46","datavalue":{"value":{"amount":"+0.88836145","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":"Q918697$C6C9AB44-5B43-44B2-8450-B6787B82927B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"484b0c0b19317817919fe9f1699b8bb813991582","datavalue":{"value":{"entity-type":"item","numeric-id":3522963,"id":"Q3522963"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cf134998b3951ddf42f373514e75404bd8987141","datavalue":{"value":{"amount":"+0.87918353","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":"Q918697$91ABB0F4-6642-40BB-B57E-48C5477A5757","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4a5c3f6435b1538290444fb01296c1db128d786e","datavalue":{"value":{"entity-type":"item","numeric-id":1384186,"id":"Q1384186"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"87a5b2d32f3bec2f22cf89b57501bb5ab0b09f4d","datavalue":{"value":{"amount":"+0.8790686","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":"Q918697$B96968BC-1290-44CF-AAF3-589CAAFAFBBB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2688a46f6fc58b528974c1eddcdcc984e73193ea","datavalue":{"value":{"entity-type":"item","numeric-id":2809312,"id":"Q2809312"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8c5da043f8d206fd612a4fff275adeb9aa8ce4fb","datavalue":{"value":{"amount":"+0.876236","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":"Q918697$55E3485F-1E58-49BC-AC1E-A730DA2EF83C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"19594dba2311313e45cc0dfb34d081d6cd96a8c3","datavalue":{"value":{"entity-type":"item","numeric-id":2848780,"id":"Q2848780"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9e1ff159f329c823d78796c5d0864e600367e40b","datavalue":{"value":{"amount":"+0.8652944","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":"Q918697$01683420-0001-4873-9F52-0831FA366630","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Recognizing tough graphs is NP-hard","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Recognizing_tough_graphs_is_NP-hard"}}}}}