Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Certifying shortest vector in a lattice

  1. Jul 17, 2010 #1
    Given an n dimensional integer lattice, is it possible to certify a vector as being a shortest one in time polynomial in n?

    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?
  2. jcsd
  3. Jul 18, 2010 #2
    Typo: basics = basis
  4. Jul 19, 2010 #3
    The first half seems to be a difficult problem. In a general case of a non-integer lattice, all that is known is that the problem of finding the shortest vector is NP-hard, so, it is not currently known whether there's a method to verify a solution in polynomial time. And, unless you place a limit the length of basis vectors, there's no reason to expect that "integerness" would let you reduce complexity.
  5. Jul 19, 2010 #4
    What about the second part? In 2 dimensions, Gauss' basis reduction runs in linear time (I think), and finds the shortest vector. In higher dimensions I've yet to see something similar.
  6. Jul 19, 2010 #5


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    I would be surprised if the algorithm time relied on the length of the longest basis vector. Otherwise you could just scale your lattice by a factor of a thousand, run your algorithm super fast, then multiply the resulting vector by 1000. Unless I'm missing something
  7. Jul 19, 2010 #6
    Since we're talking about integer lattices, you can't scale arbitrarily. Even if we're talking about rational lattices, scaling does not change the amount of bits necessary to represent a vector. Unless I misunderstood you.
  8. Jul 19, 2010 #7
    There is an algorithm to solve the whole problem exactly in 2^O(n) time: M. Ajtai, R. Kumar, and D. Sivakumar. A sieve algorithm for the shortest lattice vector problem, 2001. 2^O(n) is strictly less than O(k^n), if I'm not mistaken.

    Edit: less for large enough k. The original paper by Ajtai & co. does not quantify the multiplier in O(n).

    I don't understand any of the proofs or algorithms nearly well enough to adopt them to the specific task at hand... I wonder what it would mean to solve the problem rigorously as originally posited in the thread? Probably at least a publishable paper; not enough for a PhD thesis...
    Last edited: Jul 20, 2010
  9. Jul 19, 2010 #8


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Somehow I missed the integer part
  10. Jul 20, 2010 #9
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Similar Discussions: Certifying shortest vector in a lattice
  1. Lattice question (Replies: 4)