On the hardness of approximating shortest integer relations among rational numbers

Given x small epsilon, Greek Rn an integer relation for x is a non-trivial vector m small epsilon, Greek Zn with inner product <m,x> = 0. In this paper we prove the following: Unless every NP language is recognizable in 
Given x small epsilon, Greek Rn an integer relation for x is a non-trivial vector m small epsilon, Greek Zn with inner product <m,x> = 0. In this paper we prove the following: Unless every NP language is recognizable in deterministic quasi-polynomial time, i.e., in time O(npoly(log n)), the &#8467;infinity-shortest integer relation for a given vector x small epsilon, Greek Qn cannot be approximated in polynomial time within a factor of 2log0.5 &#8722; small gamma, Greekn, where small gamma, Greek is an arbitrarily small positive constant. This result is quasi-complementary to positive results derived from lattice basis reduction. A variant of the well-known L3-algorithm approximates for a vector x small epsilon, Greek Qn the &#8467;2-shortest integer relation within a factor of 2n/2 in polynomial time. Our proof relies on recent advances in the theory of probabilistically checkable proofs, in particular on a reduction from 2-prover 1-round interactive proof-systems. The same inapproximability result is valid for finding the &#8467;infinity-shortest integer solution for a homogeneous linear system of equations over Q.
show moreshow less

Metadaten
Author:Carsten Rössner, Jean-Pierre Seifert
URN:urn:nbn:de:hebis:30-12481
Document Type:Article
Language:English
Date of Publication (online):2005/07/19
Year of first Publication:1996
Publishing Institution:Univ.-Bibliothek Frankfurt am Main
Release Date:2005/07/19
Tag:Approximation algorithm ; Computational complexity ; Integer relations ; Label cover ; NP-hard ; Probabilistically checkable proofs
Source:Computing: The Australasian Theory Symposium (CATS) '96 , http://www.mi.informatik.uni-frankfurt.de/research/papers.html
HeBIS PPN:22477851X
Institutes:Mathematik
Informatik
Dewey Decimal Classification:510 Mathematik
Sammlungen:Universitätspublikationen
Licence (German):License Logo Veröffentlichungsvertrag für Publikationen

$Rev: 11761 $