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 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 ...
Download full text files
Additional Services
| Author: | Carsten Rössner, Jean-Pierre Seifert |
|---|---|
| URN: | urn:nbn:de:hebis:30-12498 |
| Document Type: | Report |
| Language: | English |
| Date of Publication (online): | 2005/07/19 |
| Year of first Publication: | 1997 |
| Publishing Institution: | Universitätsbibliothek Johann Christian Senckenberg |
| Release Date: | 2005/07/19 |
| Page Number: | 12 |
| Note: | auch in: 21st International Symposium on Mathematical Foundations of Computer Science (MFCS '96); Lecture Notes in Computer Science, Springer-Verlag, 1996 |
| 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: | Informatik und Mathematik / Mathematik |
| Informatik und Mathematik / Informatik | |
| Dewey Decimal Classification: | 5 Naturwissenschaften und Mathematik / 51 Mathematik / 510 Mathematik |
| Licence (German): |  Deutsches Urheberrecht |
