Hardness of approximating the Minimum Solutions of Linear Diophantine Equations

详细信息	查看全文 | 推荐本文 |

• 作者：Wenbin Chen ; Jiangtao Meng
• 关键词：NP-hardness ; Computational complexity ; Linear diophantine equations ; Approximation
• 刊名：Theoretical Computer Science
• 出版年：2007
• 期刊代码：114_03043975
• 类别：cp
• 出版时间：20 April 2007
• 卷：374
• 期：1-3
• 页码：191-195
• 文件大小：181 K

摘要

Let 1≤p<∞ be any fixed real. We show that assuming P≠NP, it is hard to approximate the Minimum Solutions of Linear Diophantine Equations in a5011333683901a51394359540b" title="Click to view the MathML source">ℓ_p norm within any constant factor and it is also hard to approximate the Minimum Solutions of Linear Diophantine Equations in ℓ_p norm within the factor 01a27b7a6b500f93d8e659677e1" title="Click to view the MathML source">n^c/loglogn for some constant c>0 where n is the number of variables in the equations.