Given an n dimensional integer lattice, is it possible to certify a vector as being a shortest one in time polynomial in n?(adsbygoogle = window.adsbygoogle || []).push({});

If we then fix the dimension n, is it possible to certify the shortest-ness in time strictly less than O(k^n) where k is the length of the largest basics vector?

**Physics Forums - The Fusion of Science and Community**

Dismiss Notice

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Certifying shortest vector in a lattice

Loading...

Similar Threads - Certifying shortest vector | Date |
---|---|

Vector Notation in Nolting Theoretical Physics 1 | Monday at 10:21 PM |

I Finding shortest distance between skew lines, checking work. | Aug 4, 2016 |

A check: shortest distance from point to line | Jan 19, 2016 |

Proof the shortest path on a sphere is the great circle. | May 10, 2015 |

Shortest path problem with multiple goals on a grid | Jan 5, 2013 |

**Physics Forums - The Fusion of Science and Community**