{"entities":{"Q1878613":{"pageid":1889355,"ns":120,"title":"Item:Q1878613","lastrevid":48341938,"modified":"2026-01-04T10:25:08Z","type":"item","id":"Q1878613","labels":{"en":{"language":"en","value":"Approximating CVP to within almost-polynomial factors is NP-hard"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 2099074"}},"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":"Q1878613$7A14BAB6-F502-4CCD-A538-BA2528B253B2","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"dfa79ac2aafb2efe685c687ef3b4f972b9b7e7c6","datavalue":{"value":{"text":"Approximating CVP to within almost-polynomial factors is NP-hard","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1878613$71D1C166-A4EE-4B53-8CC9-E2A16039E60D","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"006a277b8641ded283029fbc5d004f12efd61b94","datavalue":{"value":"1049.68072","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1878613$80D4F187-91D9-4865-AA4D-3BF675A6A158","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"b481d9d1e1fd6339de38d10a65dabc0f21090cc0","datavalue":{"value":{"entity-type":"item","numeric-id":168589,"id":"Q168589"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1878613$997A1546-FDB7-445B-B48B-E33E3D306CAB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d53c68acdd7f1baf096686dc4cd140fb6dc911d0","datavalue":{"value":{"entity-type":"item","numeric-id":645128,"id":"Q645128"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1878613$D0B09520-F258-420F-AC01-56B753768DB8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"b30ea4be0bda84f0ec06cd91b0280b36fe9cbe91","datavalue":{"value":{"entity-type":"item","numeric-id":430832,"id":"Q430832"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1878613$6C856D7D-3C37-4711-B122-00EE6C97714B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"0d14ec0d2c25271c51dc324d4a7cd01ba1a383ba","datavalue":{"value":{"entity-type":"item","numeric-id":178481,"id":"Q178481"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1878613$DB45126E-6DBB-4C8C-8CF4-9E6D1CF8B0F7","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"a87e84d22579e69c48ca0a6d828473db4dde3dd6","datavalue":{"value":{"entity-type":"item","numeric-id":168579,"id":"Q168579"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1878613$EBEF2025-95BF-43E7-BA94-923494FCAFF0","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"65aed4952f0ea543318f530fb41d65bb13a32cde","datavalue":{"value":{"time":"+2004-09-07T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1878613$8EDA1E41-46EC-4E12-B047-313AABAF3789","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"a1941b392b41701e4d3320be297a5fbeeb6093cd","datavalue":{"value":"The lattice \\(L(v_1,\\dots,v_n)\\) for linearly independent vectors \\(v_1,\\dots,v_n\\in R^k\\) for some \\(k\\) is the set \\(\\{a_1v_1+\\dots+a_nv_n\\mid a_1,\\dots,v_n\\in \\mathbb Z\\}\\). The Closest Vector Problem (CVP) consists of, given a lattice \\(L\\) and a vector \\(y\\), finding a vector in \\(L\\) with minimal distance (in a certain norm) to \\(y\\). This problem has been studied for more than 100 years. It is known to be NP-hard for any \\(l_p\\) norm. Moreover, it is known that if CVP can be approximated to within any constant factor then \\(\\text{NP} = \\text{P}\\), and that if CVP can be approximated to within a factor \\(2^{(\\log n)^{1-\\epsilon}}\\) (for any \\(\\epsilon>0\\)) then \\(\\text{NP}\\subseteq\\text{DTIME}(2^{(\\log n)^{O(1)}})\\).  The present paper proves better non-approximability results: It is shown that if CVP can be approximated to within a factor of \\(2^{\\log n\\over\\log\\log n}=n^{1\\over\\log\\log n}\\) (for any \\(\\epsilon>0\\), so-called ``almost polynomial factors'') then \\(\\text{NP} =\\text{P}\\). The proof involves a problem, called Super Sat in the paper, which might be interesting in its own right. It can be seen as a gap version of the well-known constraint satisfiability problem for finite domains.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1878613$1B894A98-EC8F-4BEE-8654-9B1372CEDDA9","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"9cda603722202722f19339c0e84295bbe19098fb","datavalue":{"value":{"entity-type":"item","numeric-id":208765,"id":"Q208765"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1878613$1AFC016D-021A-454E-8C8A-A087760BB538","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1878613$3284CC2D-DE85-4875-9783-C838A74995D0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1878613$778F100E-D0A8-4091-AC03-63D70842B858","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"b8995dd0f12bd8f23b64af5b140a4fd818044151","datavalue":{"value":"2099074","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1878613$66E154E7-DFB0-4F26-AFD9-971B9ADDED19","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"dbce712c223ceb8edc80e7e740eacce27a45cd71","datavalue":{"value":"closest vector problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1878613$EEC7775A-26BD-402B-B330-96C25A02D556","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b6f32b600ac4530cac154514c356f46339ea424d","datavalue":{"value":"lattice problems","type":"string"},"datatype":"string"},"type":"statement","id":"Q1878613$CE762BA6-2182-4959-B984-F1CB9EDBF5B6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"dc058f54aac0023b7543c366366b86bc4e72c56b","datavalue":{"value":"approximation","type":"string"},"datatype":"string"},"type":"statement","id":"Q1878613$727A99F5-57F1-4BA6-8D32-2431CC0AA37D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c7d5e4886aa4290eca104cd0d1da319d8b4d34c4","datavalue":{"value":"NP-hardness","type":"string"},"datatype":"string"},"type":"statement","id":"Q1878613$B27B91F7-2FC3-4E4A-8CBB-ACC547A5CD96","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e36edb53b4c4187925cf368d099374ffc58b2e8f","datavalue":{"value":"Super Sat","type":"string"},"datatype":"string"},"type":"statement","id":"Q1878613$28305921-F2DA-45F0-9498-307BB81BEA0F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5df0db02f69a4df23b3e1d60c98a231eaf8141df","datavalue":{"value":"constraint satisfiability problem for finite domains","type":"string"},"datatype":"string"},"type":"statement","id":"Q1878613$1B64A998-4060-426A-8295-596B88CD6BD5","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":"Q1878613$D9E0DA6B-3AA3-459C-B4F0-31BA3DB67039","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"8e6c5a8dc2d6d8ae6c54ca7e14d69c74042abccc","datavalue":{"value":"https://doi.org/10.1007/s00493-003-0019-y","type":"string"},"datatype":"url"},"type":"statement","id":"Q1878613$C5DEEA8C-01B9-4209-B346-4D2ECC5960F0","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"e50af4e6dae187e8e1cd812c3d2c9c8674184272","datavalue":{"value":"W3014312596","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1878613$91734AA3-83D5-4E37-8205-7BBF2D98AB37","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"c47178d38ab51a67db87d18a02aaac6d340f1a0b","datavalue":{"value":"Q57567992","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1878613$D321C825-ECBE-4F02-B5C7-73AAA84DBEEA","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"ac4bd070edfeb051fd83fa4e87132e62cbbafcf5","datavalue":{"value":"10.1007/S00493-003-0019-Y","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1878613$E83526E2-DD3D-457E-A8B7-C8803FA2EEE8","rank":"normal"}],"P1643":[{"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":"4d7f182ab27743aa744efa9ad627d27374ce50ca","datavalue":{"value":{"amount":"+0.8429510593414307","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":"Q1878613$39FC1C6A-0DC0-4FD5-980F-2483F4DBCD35","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":"e5075c55e02405324957bda8512663413729727e","datavalue":{"value":{"amount":"+0.8403045535087585","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":"Q1878613$02B6EDCB-0DCF-45D9-8720-76CFF8C03498","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a8cea008aac21dd96961420100bf81ce583498a1","datavalue":{"value":{"entity-type":"item","numeric-id":1589481,"id":"Q1589481"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3deb3aa719722b53790992b73b552831839ea1b6","datavalue":{"value":{"amount":"+0.8401947617530823","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":"Q1878613$B14F0135-0C51-4D5C-9EFB-4DE15A2225B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bf1189ca6e824d6762590fc4fcc457de2298b0e4","datavalue":{"value":{"entity-type":"item","numeric-id":1198041,"id":"Q1198041"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6269d60e1d67e8ac059bdd8fbda4936593a055da","datavalue":{"value":{"amount":"+0.8395196795463562","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":"Q1878613$87ECDB78-D237-42A8-AFF8-E0F10D0CB96D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"12618fec18e6f40c008bf74e371204408732d8b7","datavalue":{"value":{"entity-type":"item","numeric-id":4503941,"id":"Q4503941"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"928e7197bc307cee3bac5f944feec06694c7ddb7","datavalue":{"value":{"amount":"+0.8392924070358276","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":"Q1878613$38238ECC-F5E9-4BB8-80FC-69859404F63F","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1878613","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1878613"}}}}}