{"entities":{"Q4962605":{"pageid":6992186,"ns":120,"title":"Item:Q4962605","lastrevid":58363545,"modified":"2026-04-04T21:43:22Z","type":"item","id":"Q4962605","labels":{"en":{"language":"en","value":"On problems as hard as CNF-SAT"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6972766"}},"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":"Q4962605$F5CC4705-F19B-4D2F-BD03-34692BF27E68","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"30591a0187de0068c6daee8c0eac2f3c0e9798a2","datavalue":{"value":{"text":"On Problems as Hard as CNF-SAT","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q4962605$E331A581-150A-40BF-8D60-F78115283539","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"db8d05ec3dc76a503a7c357831928103a853ff40","datavalue":{"value":"1442.68064","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4962605$33ABE445-8F24-4E99-A5BB-C5E8F57CE757","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"b0ea64f73749f5f7d42900077771b80623f7cebf","datavalue":{"value":"10.1145/2925416","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4962605$7E7CA308-A0FA-48FE-B55B-6C10943CBCC3","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"126ad086c11d29b44b6dea551efd67f8beb1ce87","datavalue":{"value":{"entity-type":"item","numeric-id":255282,"id":"Q255282"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4962605$6862706B-70AC-4C12-BDE1-9F2DCB37D64B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"dfb3ff06d109b1edae59c508e43e1eea36ca2170","datavalue":{"value":{"entity-type":"item","numeric-id":309800,"id":"Q309800"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4962605$A1B0972B-E074-49A4-89A8-B58721923CAF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"eeb4c89d5d605ec5921eaba11728477f0fd055d5","datavalue":{"value":{"entity-type":"item","numeric-id":270004,"id":"Q270004"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4962605$563B3A59-DFBD-4BB4-8A21-F48B1962B347","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"7d363cb3f47628078b3b27b047f92db7ec1a5ada","datavalue":{"value":{"entity-type":"item","numeric-id":300459,"id":"Q300459"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4962605$7AFE80F3-C930-46D5-9665-7BC7A1F5BC9C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"3b0da0a22701b23d442fc12599227b3a3a472480","datavalue":{"value":{"entity-type":"item","numeric-id":344518,"id":"Q344518"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4962605$440F2769-B88B-4BC6-B93C-727FD149DDE9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"588f81d5d873db739b77dc3bd5e8c0569a577232","datavalue":{"value":{"entity-type":"item","numeric-id":304266,"id":"Q304266"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4962605$07C56BC4-DAA9-4A40-A582-0E02265AF3B4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d72b6c9fa09679ee04e7df5acd3659b335857c59","datavalue":{"value":{"entity-type":"item","numeric-id":192223,"id":"Q192223"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4962605$9D354C83-D420-42A9-B905-4DCD7AF24551","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"31c0d4a00f475577a11aceb1985d009cf97e6c2b","datavalue":{"value":{"entity-type":"item","numeric-id":261392,"id":"Q261392"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4962605$DBAC2DD2-18D1-464E-97FA-D7C597AAFB12","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"11324fa342c81c30ac095bea5b5286aa7a4bc5ff","datavalue":{"value":{"entity-type":"item","numeric-id":309798,"id":"Q309798"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4962605$C53FA2AC-86B4-4351-A458-6D0C9A8B6CF8","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"b2ddb6a503bb5972a5f95aecbd260c8599d794bc","datavalue":{"value":{"entity-type":"item","numeric-id":2799475,"id":"Q2799475"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4962605$4934594E-9457-4EDC-BB24-9FB982E872DC","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"aa52e5275a0a48fdb54409ff403b7de34344c3c7","datavalue":{"value":{"time":"+2018-11-05T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q4962605$ADDFBDAD-FF0C-4D15-8577-8F24233B0D80","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"18a0b1d056b35f7f7344f3f0087fcc947adeae73","datavalue":{"value":"https://arxiv.org/abs/1112.2275","type":"string"},"datatype":"url"},"type":"statement","id":"Q4962605$5401A1B2-9155-498B-8652-B708B9D4560C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"35c6be52b092a332a1cd379451dcf5c9ad4e09e2","datavalue":{"value":"http://eprints.sztaki.hu/9047/","type":"string"},"datatype":"url"},"type":"statement","id":"Q4962605$3AC3F2DD-045F-4F56-BC99-CB349C3BB3FE","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4962605$92BE9CBA-C9B5-47EC-8162-3E32EDADA2AF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"4a5372688a0d668805df5d9ffd1da58833a0f595","datavalue":{"value":"68R05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4962605$E8BD191E-CDC5-45E9-8672-81C448192619","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"7083a5d146d78edf9fc7469a5d9b0c104122f1b7","datavalue":{"value":"68R07","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4962605$99887DB1-BEE6-4063-93AC-67702FEF1CE4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4962605$0ABCA583-5FEF-4BE1-BD9A-60867FAB5A31","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a7ddaa80bf0a693a36c1113ff6b7ad576f729940","datavalue":{"value":"68W40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4962605$F1BD0957-6008-4E6B-8847-E674A1E46D9C","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"52af4da0a3a42ff97472de25e97c6bd2d796ef3b","datavalue":{"value":"6972766","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4962605$E6A3A875-D87C-45DB-AAC6-5186B28A343B","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"210aa517886edc543bc176a24e45c73173ed1975","datavalue":{"value":"optimal growth rate","type":"string"},"datatype":"string"},"type":"statement","id":"Q4962605$6828F809-98B1-47DC-9B28-D2267652714D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cfc1c912dbc1f534d35dfe4c7b828346e80b5fd8","datavalue":{"value":"reduction","type":"string"},"datatype":"string"},"type":"statement","id":"Q4962605$1E9481FA-91B2-494B-B94F-0C065B24EBA2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"252f9f9ed9fe8ca406cc19fba38a46c0414791ee","datavalue":{"value":"satisfiability","type":"string"},"datatype":"string"},"type":"statement","id":"Q4962605$2AB2C075-B852-40BD-BB16-83E7980552BD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"12dbf5e7082356c2465680d634f186cf65fa449b","datavalue":{"value":"strong exponential-time hypothesis","type":"string"},"datatype":"string"},"type":"statement","id":"Q4962605$05D01A55-C448-4B5A-A37D-6DED9610D6F9","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":"Q4962605$B6C5C447-3EBF-4E9A-B089-EFBEC8D6DD1B","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"cb425ed2bbcd2cc5663349e2d310a03b657e7c4c","datavalue":{"value":"W2404960361","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4962605$FDEDDF4C-EAAC-4276-B8E8-3DE0870CFB39","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"755bb9e2da3e04a3fdd2a172851bfa20892491a7","datavalue":{"value":{"entity-type":"item","numeric-id":5943094,"id":"Q5943094"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b830feab41de7a64c277fb702048c543a87fb17f","datavalue":{"value":{"amount":"+0.8227334022521973","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":"Q4962605$125BD4EA-DE3C-442F-AFE9-EF90B58F8AF9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3d6a9840034335c4de344169f12e12a5c7c6d978","datavalue":{"value":{"entity-type":"item","numeric-id":5741801,"id":"Q5741801"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6515e6b0e41303c1b865d42745f6c0d005c9a25b","datavalue":{"value":{"amount":"+0.8202929496765137","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":"Q4962605$5DF79F69-1443-4FD4-A240-E5980FAE5A4F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bb30208f77df467623f4ae5e8da6fd11a46bf8c0","datavalue":{"value":{"entity-type":"item","numeric-id":1604206,"id":"Q1604206"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cda748fa07ab87ca8890cb31c816df6b976ef830","datavalue":{"value":{"amount":"+0.8175631761550903","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":"Q4962605$30CA037D-030A-48CE-B9D7-47F8BEB3FF4F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5831d0bb07421d16ea3f46ba1fd616245dc1f8a8","datavalue":{"value":{"entity-type":"item","numeric-id":5417690,"id":"Q5417690"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cda748fa07ab87ca8890cb31c816df6b976ef830","datavalue":{"value":{"amount":"+0.8175631761550903","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":"Q4962605$59E1A466-62B2-450A-9AC6-EF118F0EE3B2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6d95fbb50472908c17ccd14fcd423092b2fa7352","datavalue":{"value":{"entity-type":"item","numeric-id":5868883,"id":"Q5868883"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4971d14e07b21a8181e5befa515cbc273bc82952","datavalue":{"value":{"amount":"+0.8125900030136108","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":"Q4962605$0652BAB5-FE4D-42D9-AA7E-8B4F45B48A3D","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:4962605","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:4962605"}}}}}