3.24讨论班:近似CVP判定版本与优化版本的相互规约

given a GapCVP
you input lattice basis B of int[m][n], target vector t of int[m], appr factor y, query dist r
the oracle promises to output
yes, if dist(格,目标向量)<=查询距离r
no, if dist(格, 目标向量)>yr

appr optCVP
you input B,y output a appr closest dist d∈[dist, ydist]

claim: you can figure out GapCVP, with the help of appr optCVP oracle
proof:
If (B,t,y,r) a yes instance of decision problem, then dist<=r, we get d=apprCV(B,t),
we can use d as witness,
isSmaller_appr(B,t,y,r)
d=apprCV(B,t,y)
// dist<=d<=ydist
if d<=yr, return yes
//自然问, 如果是yes实例, 能确保返回yes吗?此时, d<=ydist<=yr
if d>yr, return no
//自然问, 如果是no实例, 能确保返回no吗?可以的, no实例就有dist>yr, 这时候的d肯定满足d>=dist>yr, 所以no实例必然给返回no回答.
remark: 如果是dist∈(r,yr], 那么不能确保返回的是yes还是no.
也就是说对输入实例(B,t,y,r), 问GapCVP, 返回yes, 只能推断成立dist<=yr
返回no, 只能推断dist>r.

claim: you can figure out a appr closetst dist d, with the help of GapCVP oracle

我们按照如下的procedure给出一个d, 满足d>=dist且d<=ydist
现在dist不知道.dist的下界为1.
从1出发, 则[1,y],(y,y^2]..(y(n-1),y^n]这有限个区间里面, dist一定只落在其中的一个中
比如dist落在区间(y^(k-1),yk], 那么返回d=y^k即可.
现在解题者取r=1,
Y:若oracle说Yes, 则意味着dist<=y, 又dist>=1, 所以此时取d=y, 那么一方面y>=dist成立, 一方面y<=y^dist, 所以此时return y即可.
N:不然, oracle说No, 则意味着dist>1,
再次问oracle with r=y,
NY:若回答Yes, 则意味着dist<=y^2,此时, 关于dist我们知道 dist∈(1,y^2], 这时候, 若dist<=y的,则上一次问oracle, 就不会回答No了,所以只能是dist>y, 所以dist在(y,y^2]里面, 此时return y^2
NN:若回答No, 则意味着dist>y, 此时关于dist有dist∈(y,inf)
继续问oracle with r=y^2
NNY:若回答Yes, 则意味着dist<=y^3, 此时关于dist有dist∈(y,y^3], 若dist<=y^2, 则上一次就不会回答No, 所以dist∈(y^2,y3], 此时return y^3
.
.
.
k个N: 因为dist是个有限数, 所以必然存在某个k, 使得dist(y^k,y(k+1)], 当问了k次oracle后回答都是No, 就意味着dist>y^(k-1).
继续问oracle with r=y^k
k个N一个Y:若回答Yes, 则dist<=y^(k+1), 若dist<=y^k, 则上一次就不会回答No, 所以dist∈(y^k,y(k+1)], return y^(k+1).
程序必然在这里终止,
如果程序继续, 则会超出dist的上界.

findCV_appr(B,t,y)
r=1
flag=false
while(true)
  flag=gap(B,t,y,r)
  if(flag==true) return y*r
  else r=y*r