文献

J-GLOBAL ID：201602273616723503   整理番号：16A0901467

SVP(最短ベクトル問題)オラクルによる低密度多重部分集合和問題の解法【Powered by NICT】

Solving Low-Density Multiple Subset Sum Problems with SVP Oracle

著者 (2件)： Pan Yanbin (Academy of Mathematics and Systems Science) ,  Zhang Feng (Academy of Mathematics and Systems Science)
資料名： Xitong Kexue Yu Fuza Xing Xuebao  (Xitong Kexue Yu Fuza Xing Xuebao)
巻： 29  号： 1  ページ： 228-242  発行年： 2016年 
JST資料番号： C2850A  ISSN： 1009-6124  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： 中国 (CHN)  言語： 英語 (EN)

抄録/ポイント： 0.9408以下のほとんどすべての部分集合和の問題は,特殊な格子における最短ベクトルを見つけることができることをSVPオラクルによる多項式時間で解くことができることが知られている。本論文では,著者らは,正確に同じ溶液によるk部分集合和問題を持つK多重部分集合和問題のためのある類似の結果であることを示した。特に,単一部分集合和問題(k = 1)のための,修正格子は提案した解析はより簡単であり,前よりも緊密な成功確率の限界を紹介した。さらに,多重部分集合和問題の拡張版についても考察した。Data from the ScienceChina, LCAS.【Powered by NICT】

シソーラス用語： 多重化 ,  *部分集合 ,  ベクトル
準シソーラス用語： 多項式時間 , 【Automatic Indexing@JST】

著者キーワード (4件)： 格子 ,  低密度 ,  多重モジュラ部分集合和問題 ,  多重部分集合和問題

分類 (1件)： 計算理論  (JB02000A)

タイトルに関連する用語 (7件)： ベクトル ,  オラクル ,  低密度 ,  多重 ,  部分集合 ,  問題 ,  解法