A.k.a. SVP, a.k.a. korteste vektor-problem. Eksakt versjon er ikke i [[NP]] (man vet ikke a priori lengden på den korteste vektoren), men er kjent til å være [[NP]]-hardt under infinity norm, og [[NP]]-hardt under $\ell_2$-norm *men* under randomisert reduksjoner (altså, reduksjonene til de andre problemene i [[NP]] benytter tilfeldighet), slik at vi kan bare konkludere med at det er [[NP]]-hardt dersom [[BPP]] = [[P]] (som ikke er usannsynlig). Man kan lage en variant av problemet som *ligger* i [[NP]] ved å oppgi en maks lengde $k$, og spørre hvorvidt det eksisterer en vektor med lengde mindre enn eller lik $k$. Ja-instanser blir dermed lett å verifisere, men nei-instanser lar seg faktisk også lett verifisere ved å oppgi den "peneste mulige" (altså maksimalt ortogonale) basisen til gitteret. Dermed er *Approximate SVP* faktisk i [[NP]] $\cap$ [[coNP]], og er dermed *ikke* [[NP]]-komplett. Oded Regev viste via en kvantereduksjon at en effektiv algoritme for [[Learning with errors]] impliserer en effektiv kvantealgoritme for SVP. Dersom [[Chens algoritme]] viser seg å være korrekt, vil dette dermed plassere SVP i [[BQP]], som kanskje vil være det største gjennombruddet i kvantealgoritmer siden [[Grovers algoritme]]. Fra et [[Shtetl-Optimized]] [kommentarfelt](https://scottaaronson.blog/?p=7946#comments): > Yes, there appear to be phase transitions in the hardness of SVP depending on the approximation ratio, although it’s a major open problem to pin down exactly where they happen. For example, SVP with constant (or even slightly super-constant) approximation ratio is known to be NP-hard. SVP with √n approximation ratio still seems to be hard (?), but it’s almost certainly not NP-hard, since Aharonov and Regev showed that it’s in NP∩coNP. And SVP with some exponential approximation ratio can be done in classical polynomial time using the LLL algorithm. - [[Scott Aaronson]] Fra [[NaCl]]-foredrag [[12024-06-05]]—se spesielt linjen på bunnen: ![[IMG_6609 1.jpeg]] ### Survey ![[Pasted image 20240730143600.png]] https://eccc.weizmann.ac.il/report/2022/170/