定理: 給decisionalCVP oracle, 可以有效解決searchCVP.
這里格和目標向量都在整點上取值, 格的秩為n. int[m][n] B, int[m][1] t.
證明:
首先, 是可以由判定器確定出最近距離是多少的.
對于任一格B,及目標向量t, 設r=dist(B,t), 下面估計r的上界.
令R:=|b1|+...+|bn|
t = t1b1+t2b2+...+tnbn
g=floor(t1)b1+...+floor(tn)bn
設g0是searchCVP的精確解,下用{x}表示數x-floor(x)
則|g0 - t| <=|g - t|=|{t1}b1+...+{tn}bn|<=|b1|+...+|bn|=R,
所以借助decisionalCVP oralcle, 利用二分法可以確定出optCVP.
最多問log(R^2)次, 這對于input size來說是多項式的.

一個觀察是稀疏格的最近向量問題是容易解決的.
按照最近平面算法(the Nearest algorithm):

findCV_appr(B,t)
t=proj(t,spanB)
B~=GS(B)
b=t
for j=n to 1 do
  b=b-round(miu(b,GS(B.col j)))*B.col j
return t-b

或者是寫成遞歸調用的形式:

findCV_appr(B=[b1,...,bn],t)
if n=0 then return 0
else 
    B~=GS(B)
    s=proj(t,span(b1,...,bn))
    //find c s.t. the hyperspace c\*GS(B.col n)+span(b1,...,b n-1) 
    // as close as possible to s
    c=round(miu(b,GS(B.col j)))
    return c*bn+findCV_appr(B=[b1,...,b n-1], t-c*bn)

關于目標向量投影的注記
對于CVP, 目標向量t如果不在span(B)里面, 可以將t投影到其上.
設投影向量為t' , 如果 y 是離 t' 最近的格向量, 那么 y 是離 t 最近的格向量.
Claim: If y=searchCVP(B, t'), x=searchCVP_gamma(B,t')
then y=searchCVP(B,t), x=searchCVP_gamma(B,t)
由searchCVPγ(B,t')返回x, 則有|t'-x|^2<=γ2 |t'-y|^2.
因為t-t'正交與span(B), 所以有t-t'垂直于t'-x和t'-y, 故而有下式:
|t-y|^2=|t-t'|2(常值)+|t'-y|^2(投影里最近距離)
所以y=searchCVP(B,t);
|t-x|^2=|t-t'|2+|t'-x|^2
<=|t-t'|^2+γ2 |t'-y|^2
<=γ^2(|t-t'|2+|t'-y|^2)
=γ^2*|t-y|2
所以 x=searchCVP_gamma(B,t).

令 u = findCV_appr(B,t),
則|u-t|<=2^(n/2)dist(t,L(B))

我們的目標向量變?yōu)?strong>原目標+某個格向量, 對這個新目標來求最近向量的問題, 然后再把這個附加的格向量減掉, 就可以得到真正要求的了. 下面要做的就是稀疏化原來的格.

k取n+ceil(log r)

Sparser_1(B1,tt)
//其中B1張成了格L(B)的子格
//tt是t+v的形式, v是L(B)中的格向量    
B'=(2*B1.col1, B1.col2, ...,B1.col n)
if B'.col1>=2^k*B.col 1 return (B', tt)
ans=isSmaller(L(B'), tt, r)
//query decisional CVP oracle
if ans==true 
//t1離更稀疏的B'的距離小于等于r, 此時dist*(L(B'),tt)>=r
//那么說明dist(L(B2),tt)==r
  Sparser_1(B',tt) //t2=t1
else //t1離B2的距離大于r, 即稀疏化以后, 離格的最近距離遠了
  tt=tt-B1.col1
  Sparser_1(B',tt)
return (B',tt)

1.B'是B1的子格, B1是B的子格, 所以B'是B的子格
2.調用一次Sparser_1, tt要么不變, 要么變?yōu)閠t-B1.col1, 都是 t+格點 的形式
3.最后返回的(B',tt), 滿足dist(L(B'),tt)==r(本算法的關鍵)
事實上, 如果isSmaller == true, 上式成立
如果isSmaller == false, 注意到L(B1)=L(B')U(L(B')+B1.col1),
這說明在L(B')+B1.col1里面取格點達到最近向量,
所以dist(L(B')+B1.col1,tt)==r, 這等價于
dist(L(B'),tt-B1.col1)==r

Sparser_2(B1,t)
//改動部分如下, 其他處理不變
B'=(B1.col1, 2B1.col2, ...,B1.col n)
if B'.col2>=2^kB.col 2 return (B', tt)

于是我們可以給出求解searchCVP的程式

findCV(B,t)
t0=t
for i=1 to n do
  (B,t)=Sparse_i(B,t)
g=findCV_appr(B,t)
v=t-t0
return g-v

從Sparser_1到Sparser_n, 共有n*k次迭代步驟
在n*k步以后, 得到(B*,t*)
B*=(2^k*b1,...,2k*bn)
t*=t+某格點v
由k=n+ceil(log r), 得2^k>=r*2n
λ1(L(B*))>=2^k>=r*2n
則在L(B*)里的兩個向量距離至少為r*2^n.
離t*第一近的格點到t的距離為r, 設離t第二近的格點到t*的距離為r',
則r+r'>=r*2^n, 所以r'>=r*2^n-r>=2(n-1) r>2^(n/2)(n-1)r (n>2)
(n<=2的時候找最近向量是容易的, 窮舉很快, 因為維數很低.)
可以得到最近平面算法更優(yōu)的近似因子 γ=2(2/sqrt(3))^n.
所以findCV_appr(B*,t*)給出的最近格向量g-, 滿足
|g--t*|=dist(B*,t*)=r, 所以最后return g-v.

**Theorem: Decisional CVP is NP-complete **

• decisional CVP is NP
  對于使 dist(t, L(B))<=r 的實例 (B,t,r)
  令x為格向量, 滿足|x-t|<=r
  Claim: x 可以作為decisionalCVP為NP問題的一個證據
  |x-t|<=r可以多項式間驗證, 代入算即可
  x的每一個分量xi的絕對值至多為|t|+r
  |xi|<=|x|=|x-t+t|<=|t|+r
  Remark:本篇| |均表示算二范數

• decisional CVP is NP-hard
  a reduction from subset-sum problem
  an instance of subset-sum:
  given n+1 integers a1,a2,...,an, s
  goal: find A, some subset of set {1,2,...,n}
  s.t. sum of ai (i ∈A)=s
  下面說明:
  若有一個子集和問題的Yes實例, 就給出了一個isSmaller(B,t,sqrt(n))的Yes實例 ;
  若有一個isSmaller(B,t,sqrt(n))的Yes實例, 就給出了子集和問題的一個Yes實例.
  而子集和問題的decision版本又是NP-hard的, 而上面這段已經說明了兩個問題可以互相規(guī)約到, 所以它們兩個的復雜性是同等級別的, 又已知子集和問題是NP-hard的, 所以第二個claim成立.
  這里的B和t的構造如下
  B[n+1][n]={
  {a1,a2,...,an},
  {2, 0, ...,0 },
  {0, 2, ...,0 },
  ...
  {0, 0, ...,2 }
  }

t[n+1][1]={
{s},
{1},
...
{1}
}
如果(a1,a2,...,an,s)是子集和問題的Yes實例, 則isSmaller(B,t,sqrt(n))是decisionalCVP的Yes實例;
如果isSmaller(B,t,sqrt(n))是decisionalCVP的Yes實例, 則(a1,a2,...,an,s)是子集和問題的Yes實例.
上面兩個方向由B和t的構造容易說明.

SVP vs CVP

對于大于等于1的近似因子γ, 找到SVP的γ-近似解的難度<=找到CVP的γ-近似解.
給一個SVP的實例, 我們用CVP的procedure, 令目標向量為0. 但是這其實不行, 因為0向量的CV就是它本身.
remove some points of lattice to make a sublattice
try several sublattices, s.t. one of which is guaranteed to reveal the desired short vector.

a generalization of decisionalCVP: GapCVPγ

It's a promise problem.
(PI_YES, PI_NO)
對于在PI_YES∪PI_NO里的一個輸入實例I, it decides I在PI_YES里還是在PI_NO里, 不像total decision problems, PI_YES∪PI_NO不必包含全部可能性

GapCVPγ:
yes 小于等于r
no >γ*r

當γ=1的時候, 就是確定性的CVP判定問題.
類似地可以給出GapSVPγ的定義

**定理(判定版): 給GapCVPγ oracle, 可以有效解決GapSVPγ **
證明: 令GapSVPγ要解決的實例為(B,r)
構造n個GapCVPγ oracle實例, 調用isCloser(格基,目標向量,查詢距離)程式

isShorter(B,r)
  flag == false
  for i=1 to n do
  Bi=(B.col1,...,2B.col i, ...,B.coln)
  bi=B.col i
  //Bi: 第i個列向量為原來B.col i的兩倍, 其他的和B的列向量相同
  //目標向量為bi
  //查詢距離為r
  if isCloser(Bi, bi, r) == true
      flag==true
      return flag
  return flag
     //至少有一個closer, 返回Yes, 每個都更遠的話, 返回no

下面證明, 用上面這個procedure, 確實可以回答GapSVPγ的問題

• 假設(B,r)是個No實例, 即有任何格向量長度都比查詢長度r的γ倍要大,
  對于每一個v ∈ L(Bi), 有v-bi ∈ L(B)-{0}, 所以|v-bi|>γ*r, 這時候isCloser(Bi,bi,r)確實返回No(對任意i).
• 假設(B,r)是個Yes實例, 即有L(B)中的最短向量長度≤r, 令v是達到最短長度的格向量, |v|≤r. v=a1b1+...+anbn, 這里ai是整數. 則這些整系數里至少有一個是奇數. 若不然, 全部系數都是偶數的話, v/2會在格里面, 那么找到了一個長度更短的格向量, 矛盾.設ak是奇數, 則bk+v ∈ L(Bk), 所以有bk+v=x ∈ L(Bk), 所以dist(bk,L(Bk))<=|bk-x|=|v|<=r. 所以isCloser(Bk,bk,r)返回了true, 所以isShorter(B,k)會返回true.
  上面說明了, 當給出Yes實例的時候, 確實會返回true; 當給出No實例的時候, 確實會返回False, 算法正確性得證.

**定理(搜索版): 給searchCVPγ oracle, 可以有效解決searchSVPγ **
證明: 令searchSVPγ要解決的實例為B, 秩為n.
構造n個searchCVPγ oracle實例, 調用findCV_appr(格基,目標向量)程式

findSV_appr(B)
  for i=1 to n do
  Bi=(B.col1,...,2*B.col i,....,B.col n)
  bi=B.col i
  //Bi: 第i個列向量為原來B.col i的兩倍, 其他的和B的列向量相同
  //目標向量為bi
  xi=findCV_appr(Bi, bi)
  k=1
  //k keeps index
  keep_dist=|x1-b1|
  for i=2 to n do
    if  |xi-bi|<keep_dist 
       keep_dist=|xi-bi|
        k=i
return xk

令v為達到最短長度的格向量, 則v的整系數表達式中, 至少有一個為奇數,該系數設為ak, 不然, 0.5倍該向量, 得到了一個更短的格向量, 矛盾. 于是v=L(Bk)的某向量 - bk, 故dist(bk,L(Bk))<=|v|,而這個距離要大于等于最短格向量的長度, 所以只能取等號.dist(bk,L(Bk))=|v|, 則|xk-bk|<=γ|v|, 所以可以返回某滿足要求的xk.

**定理(最優(yōu)版): 給optCVPγ oracle, 可以有效解決optSVPγ **

shortest_appr(B)
  for i=1 to n do
    Bi=(B.col1,...,2*B.col i,....,B.col n)
    bi=B.col i
    //Bi: 第i個列向量為原來B.col i的兩倍, 其他的和B的列向量相同
    //目標向量為bi
    di=closest_appr(Bi, bi)
  keep_dist=d1
  for i=2 to n do
    if  di<keep_dist 
       keep_dist=di
return keep_dist

令v為達到最短長度的格向量, 則v的整系數表達式中, 至少有一個為奇數,該系數設為ak, 不然, 0.5倍該向量, 得到了一個更短的格向量, 矛盾. 于是v=L(Bk)的某向量 - bk, 故dist(bk,L(Bk))<=|v|,而這個距離要大于等于最短格向量的長度, 所以只能取等號.dist(bk,L(Bk))=|v|, 由于dk是由closest_appr(Bk, bk)返回, dk<=γdist(bk,L(Bk))=γλ1,而也成立dk=dist(0,L(Bk)-bk), 所以返回的滿足optSVPγ的要求.