■

2chのスレッドで反応するのは良くないなぁと思ったので, ここにメモを残しておきます. まぁそもそも仮定につっこむのもアレですが.

格子の被覆半径を計算する問題がNPに属することをわしが証明したら、

V. Guruswami, D. Micciancio, and O. Regev "The complexity of the covering radius problem" (CCC 2004, Computational Complexity 2005) に色々結果が書かれています. この中では, GapCRP_2はAMに入ることが知られています. Exact versionについてはまだ未解決問題なんで頑張ってください.

わしが任意定数の因子内でSVPの近似することがNP困難であることを証明したら

S. Khot “Hardness of approximating the shortest vector problem in lattices” (FOCS 2004) により, NP⊆RPでないなら, 任意のl_pノルム (p<1) で近似度が定数のものについてはNP困難であることが知られています. もう少し強い仮定を置くと, 近似度が定数を超えます.
仮定を外すのは (近似度が任意の定数だとしても) 重要な未解決問題なので決定性帰着を作れるならそれは凄いことです.

頑張れ(;´Д｀)