Approximating good simultaneous diophantine approximations is almost NP-hard

Given a real vector alpha =(alpha1 ; : : : ; alpha d ) and a real number E > 0 a good Diophantine approximation to alpha is a number Q such that IIQ alpha mod Zk1 ", where k \Delta k1 denotes the 1-norm kxk1 := max 1id j
Given a real vector alpha =(alpha1 ; : : : ; alpha d ) and a real number E > 0 a good Diophantine approximation to alpha is a number Q such that IIQ alpha mod Zk1 ", where k \Delta k1 denotes the 1-norm kxk1 := max 1id jx i j for x = (x1 ; : : : ; xd ). Lagarias [12] proved the NP-completeness of the corresponding decision problem, i.e., given a vector ff 2 Q d , a rational number " ? 0 and a number N 2 N+ , decide whether there exists a number Q with 1 Q N and kQff mod Zk1 ". We prove that, unless ...
show moreshow less

Metadaten
Author:Carsten Rössner, Jean-Pierre Seifert
URN:urn:nbn:de:hebis:30-12498
Document Type:Article
Language:English
Date of Publication (online):2005/07/19
Year of first Publication:1997
Publishing Institution:Univ.-Bibliothek Frankfurt am Main
Release Date:2005/07/19
Source:21st International Symposium on Mathematical Foundations of Computer Science (MFCS '96); Lecture Notes in Computer Science, Springer-Verlag, 1996 - http://www.mi.informatik.uni-frankfurt.de/research/papers.html
HeBIS PPN:224948695
Institutes:Mathematik
Informatik
Dewey Decimal Classification:510 Mathematik
Sammlungen:Universitätspublikationen
Licence (German):License Logo Veröffentlichungsvertrag für Publikationen

$Rev: 11761 $