{"entities":{"Q1589481":{"pageid":1600221,"ns":120,"title":"Item:Q1589481","lastrevid":72267261,"modified":"2026-04-14T03:45:14Z","type":"item","id":"Q1589481","labels":{"en":{"language":"en","value":"A note on the non-NP-hardness of approximate lattice problems under general Cook reductions."}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1542286"}},"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":"Q1589481$A502E9F1-67BF-41E4-A7E7-11B596BB4C82","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"845725ccb399468af9f4d970d8438f31c82d27e2","datavalue":{"value":{"text":"A note on the non-NP-hardness of approximate lattice problems under general Cook reductions.","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1589481$33047D5E-416F-42A3-B6EA-7B16DDD4EBA9","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"e7c68782ba71c49520ef873688c9425835024c71","datavalue":{"value":"1063.11504","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1589481$51B96F3A-1836-4B72-981C-C24D40373A02","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"394405adf3479ecd5785cb06f618621cfd643929","datavalue":{"value":"10.1016/S0020-0190(00)00123-X","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1589481$A62170B9-D181-43FD-9248-9BA42C8D9910","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"153f087410d6445d3ecf9b2f61b070cffa67488f","datavalue":{"value":{"entity-type":"item","numeric-id":269464,"id":"Q269464"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1589481$C6E6A3D4-B691-436A-A2E5-44CABDF78803","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"180139f6df640572f1dadc134f69c4a263c16b02","datavalue":{"value":{"entity-type":"item","numeric-id":1589480,"id":"Q1589480"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1589481$0C96E771-DF61-4A69-96D4-FEFDBB057143","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"52fa7d44b58d0511cb8993765bd916aef86052d8","datavalue":{"value":{"entity-type":"item","numeric-id":63092,"id":"Q63092"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1589481$03D644E7-A4EF-4761-A83B-5F828D39228A","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"1fc98fd02909f39fc4d6749553781a25cceed046","datavalue":{"value":{"time":"+2000-12-12T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1589481$48F4303F-A1E8-43FE-A4C4-E69688DA46D3","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fd716104cf156585f3bce22202c836b7465d3133","datavalue":{"value":"11Y16","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1589481$C60CDD6B-9114-4094-BB4A-F730CDF793EA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6be78f1bad1f2f19058dbde65eb124c0430a7d27","datavalue":{"value":"68W30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1589481$8481BCA5-6AD3-4943-A42E-1DC65946D595","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1589481$3898B7AD-FA63-4F13-A53B-8000BDAE380E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b4346faa01bb5fb0576370374d6456afd58d5666","datavalue":{"value":"68Q15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1589481$8746A685-C52D-4434-B55A-A39E58122EC5","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"c238d070aded38ed04dbcb657baf5a4ae05cdfb7","datavalue":{"value":"1542286","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1589481$BD2721F4-A990-4A51-A0B0-431DC45198D7","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"da67da54e89e7c80f20f3f95c3ceec18bb927753","datavalue":{"value":"Computational complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1589481$743D313F-D980-4831-A1D5-B606C7516D2F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2eb0965db9d20f089882e04d76b83ab4d6c09eef","datavalue":{"value":"Collapse","type":"string"},"datatype":"string"},"type":"statement","id":"Q1589481$62C6EC9A-5975-40BF-8453-A2576E266276","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"abe786043e7fa02f963cefbd790478b7e6d0e8b5","datavalue":{"value":"General Cook reduction","type":"string"},"datatype":"string"},"type":"statement","id":"Q1589481$D1924EBF-8542-4CEA-860F-AFE9B561E915","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1c96e8fcdfc59dc3751ce725899243d2e740fa31","datavalue":{"value":"Lattice","type":"string"},"datatype":"string"},"type":"statement","id":"Q1589481$65A148AE-BE7A-4F92-B8D9-EF05D0B4573E","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":"Q1589481$98E41C04-06F5-4120-B0F5-65434F82BE99","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"702f0afed0ff12acec467dc949a7a6178a30a71a","datavalue":{"value":{"entity-type":"item","numeric-id":1356888,"id":"Q1356888"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1589481$18DB7723-AEC9-4CC6-8261-A88965355E2C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"147f4bd46ebd453c35256aaefb797a34c59684d0","datavalue":{"value":{"entity-type":"item","numeric-id":4228459,"id":"Q4228459"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1589481$55BFFEB8-F999-4179-8EBA-AB2D16324170","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1422fa73c563b7c939f4423cad8a509df12f0639","datavalue":{"value":{"entity-type":"item","numeric-id":4542515,"id":"Q4542515"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1589481$51224B02-BF47-4557-AB8B-A8F526F4A487","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0dbe517209176053770d2eb88006fc6be3776a80","datavalue":{"value":{"entity-type":"item","numeric-id":4526993,"id":"Q4526993"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1589481$D05E8201-6AB2-4BB7-96DC-0AED06A1AC7E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6c5626a150394f2bd87219771777620a536db517","datavalue":{"value":{"entity-type":"item","numeric-id":1318081,"id":"Q1318081"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1589481$73B2CD39-828E-4B92-86C2-23B922F2B99F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ac4b8e7cf4034c184fb2852754739a22a4e70036","datavalue":{"value":{"entity-type":"item","numeric-id":1108004,"id":"Q1108004"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1589481$E64F6927-BD0E-4CC4-8602-5F2DC5C218EB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"507bd51c8e0d1c0df633ceece24bd8a2ef75790b","datavalue":{"value":{"entity-type":"item","numeric-id":2819600,"id":"Q2819600"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1589481$ADD59F05-DD65-48EB-B666-42AC29DA53FA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f29811ad8170f6bd59059e35c4fd8623152d7ed1","datavalue":{"value":{"entity-type":"item","numeric-id":1274988,"id":"Q1274988"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1589481$F550ACAD-0CEA-4E17-BAB2-CC22F6021D5E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"44a30d07705b00e95a7bb40e9c7b4d81bf663310","datavalue":{"value":{"entity-type":"item","numeric-id":4281495,"id":"Q4281495"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1589481$93A6E106-87F5-4371-BB42-BDBD23C93093","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a641de2764dcca1438142905c71f0c54a457ce40","datavalue":{"value":{"entity-type":"item","numeric-id":4258570,"id":"Q4258570"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1589481$6768FE0C-0521-492B-9D43-380628C2A962","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"36d74181ce834d0ad881a8690b122494a27599a8","datavalue":{"value":{"entity-type":"item","numeric-id":1878613,"id":"Q1878613"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1589481$56DD3A68-2495-4A42-8CBD-B51073241307","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"49ee1410bd306d6722cc2c176479c826bbb0715d","datavalue":{"value":{"entity-type":"item","numeric-id":3722415,"id":"Q3722415"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1589481$E34390FF-03AD-4540-B5AD-51CE85888F49","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"505b48f00a5663350aa0151dd7cd74fd464c6284","datavalue":{"value":{"entity-type":"item","numeric-id":4542514,"id":"Q4542514"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1589481$320F3D12-8703-43E1-BE44-169A583DCD9D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b1aa96b7c0ec9bc7a683e7636e258c3fded01e42","datavalue":{"value":{"entity-type":"item","numeric-id":3787917,"id":"Q3787917"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1589481$B5A2A3E5-74E0-467D-82DF-0E9E9BB9AA60","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3ba8394390a6d59952f33324c5c063f119bd5d68","datavalue":{"value":{"entity-type":"item","numeric-id":757465,"id":"Q757465"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1589481$88FB6E4F-46D9-4B83-8F87-08D558F5779B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8fda6a9324563f1c0b86a463baa312018e84653d","datavalue":{"value":{"entity-type":"item","numeric-id":3792245,"id":"Q3792245"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1589481$04A29676-D3B5-4536-A51B-C33410A8AA5B","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"605f4c51f9f3b9d98184c53473ef87cc75519bad","datavalue":{"value":"https://doi.org/10.1016/s0020-0190(00)00123-x","type":"string"},"datatype":"url"},"type":"statement","id":"Q1589481$F8F65AD1-1A82-46D8-B10A-84EE71F2D8C9","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"235ca75d06fd499e917083552d1938981a335593","datavalue":{"value":"W2028838286","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1589481$CBDB7F45-B10B-47FB-A2DC-E8077715CFDC","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5cbdf5c4ce3b4d03076da3a87ec1eb9b163b0155","datavalue":{"value":{"entity-type":"item","numeric-id":4258570,"id":"Q4258570"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"09e670c636f074efa9c53180c345a1bfb8ac2049","datavalue":{"value":{"amount":"+0.840690553188324","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":"Q1589481$82ACCED8-7ED2-4C77-983A-94D6E6E95CD6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3c2bc21ab188204ffed3c502ef255fb9865e562a","datavalue":{"value":{"entity-type":"item","numeric-id":1961373,"id":"Q1961373"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"355dafe1841f8a37a19a61fe82e670c18ce455f1","datavalue":{"value":{"amount":"+0.8384798169136047","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":"Q1589481$6B7A2614-7344-43F4-8FB6-85243C1A4DEC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6ada8cec9642bf90b9271883fd673eabc22d78f9","datavalue":{"value":{"entity-type":"item","numeric-id":1577010,"id":"Q1577010"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"26345673bc4f9fba61f75a118bf2295b96d0f80b","datavalue":{"value":{"amount":"+0.8365167379379272","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":"Q1589481$CFE9D831-641A-43B7-A582-8C71FEA9ED91","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"129a38e46e3fef7806f67e37104167b62648b886","datavalue":{"value":{"entity-type":"item","numeric-id":1878613,"id":"Q1878613"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b53ca97558f44e43f63eb7aef9afea6e26688233","datavalue":{"value":{"amount":"+0.8333910703659058","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":"Q1589481$15959DA1-58C5-4413-AA4C-71A27A9177D3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"02795936d0b9b247a1b55678b05b394765814e11","datavalue":{"value":{"entity-type":"item","numeric-id":1608337,"id":"Q1608337"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"77808b2f9402fea91ee8831d64c7fbb4e806514c","datavalue":{"value":{"amount":"+0.8288744688034058","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":"Q1589481$E0D6A8A8-C5EC-433E-BDAE-55A4F9225D81","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A note on the non-NP-hardness of approximate lattice problems under general Cook reductions.","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_note_on_the_non-NP-hardness_of_approximate_lattice_problems_under_general_Cook_reductions."}}}}}