Approximating CVP to Within Almost-Polynomial Factors is NP-Hard

I. Dinur; G. Kindler; R. Raz; S. Safra

首页> 外文期刊>Combinatorica >Approximating CVP to Within Almost-Polynomial Factors is NP-Hard

【24h】

Approximating CVP to Within Almost-Polynomial Factors is NP-Hard

机译：NP-Hard使CVP接近于几乎多项式因子

获取原文

获取原文并翻译 | 示例

获取外文期刊封面封底 >>

开具论文收录证明 >>

文献代查 >>

团队文献服务 >>

页面导航

摘要
著录项
相似文献
相关主题

摘要

This paper shows the problem of ﬁnding the closest vector in an n-dimensional lattice to be NP-hard to approximate to within factor n c/log log n for some constant c > 0.

机译：本文显示了在某个常数c> 0的情况下，找到在n维晶格中最接近的向量是NP-hard的近似问题，该问题近似于n c / log log n 因子之内。

著录项

来源
《Combinatorica 》 |2003年第2期| 205-243| 共39页
作者
I. Dinur; G. Kindler; R. Raz; S. Safra;
展开▼
作者单位

Department of Computer Science Tel-Aviv University;

Department of Computer Science Tel-Aviv University;

Faculty of Mathematics and Computer Science Weizmann Institute of Science;

Department of Computer Science Tel-Aviv University;

展开▼
收录信息
原文格式 PDF
正文语种 eng
中图分类
关键词
68Q17;

机译：公元前68年17日;

相似文献

外文文献
中文文献
专利

1. Approximating CVP to within almost-polynomial factors is NP-hard [J] . Dinur I., Kindler G., Raz R., Combinatorica . 2003 ,第2期

机译：将CVP逼近几乎多项式因子是NP-hard
2. Approximating SVP infinity to within almost-polynomial factors is NP-hard [J] . Dinur I. Theoretical computer science . 2002 ,第1期

机译：在几乎多项式因子内将SVP无限近似为NP-hard
3. Approximating SVP{sub}∞ to within almost-polynomial factors is NP-hard [J] . Irit Dinur Theoretical computer science . 2002 ,第1期

机译：在几乎多项式因子内将SVP {sub}∞近似为NP-hard
4. Approximating-CVP to within almost-polynomial factors is NP-hard [C] . Dinur I., Kindler G., Safra S. Foundations of Computer Science, 1998. Proceedings.39th Annual Symposium on . 1998

机译：在几乎多项式因子内将CVP近似为NP-hard
5. Approximating NP-hard problems efficient algorithms and their limits. [D] . Raghavendra, Prasad. 2009

机译：逼近NP难题高效算法及其局限性。
6. IJV collapsibility index vs IVC collapsibility index by point of care ultrasound for estimation of CVP: a comparative study with direct estimation of CVP [O] . Haitham Mohammed Jassim, Vamanjore A Naushad, Mohamad Yahya Khatib, 2019

机译：IJV可折叠性指数与IVC可折叠性指数（按即时超声评估CVP的评估）：直接估计CVP的比较研究
7. Approximating-CVP to Within Almost-Polynomial Factors is NP-hard [O] . I. Dinur, G. Kindler, S. Safra 1998

机译：在几乎多项式因子内逼近CVP是NP难的

Approximating CVP to Within Almost-Polynomial Factors is NP-Hard

摘要

著录项

相似文献

相关主题

期刊订阅