Hardness of approximating the Minimum Solutions of Linear Diophantine Equations

Let 1 ≤ p < ∞ be any fixed real. We show that assuming P ≠ N P , it is hard to approximate the Minimum Solutions of Linear Diophantine Equations in ℓ 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 f...

Full description

Saved in:
Bibliographic Details
Published in:Theoretical computer science 2007-04, Vol.374 (1), p.191-195
Main Authors: Chen, Wenbin, Meng, Jiangtao
Format: Article
Language:English
Subjects:
Algebra
Algorithmics. Computability. Computer arithmetics
Applied sciences
Approximation
Computational complexity
Computer science
control theory
systems
Exact sciences and technology
Linear diophantine equations
Mathematics
NP-hardness
Number theory
Sciences and techniques of general use
Theoretical computing
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Let 1 ≤ p < ∞ be any fixed real. We show that assuming P ≠ N P , it is hard to approximate the Minimum Solutions of Linear Diophantine Equations in ℓ 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 n c / log log n for some constant c > 0 where n is the number of variables in the equations.
ISSN:0304-3975
1879-2294
DOI:10.1016/j.tcs.2006.12.023