__
Revision #1 to TR97-047 | 11th November 1997 00:00
__
#### The Shortest Vector Problem in L_2 is NP-hard for Randomized Reductions.

**Abstract:**
We show that the shortest vector problem in lattices

with L_2 norm is NP-hard for randomized reductions. Moreover we

also show that there is a positive absolute constant c, so that to

find a vector which is longer than the shortest non-zero vector by no

more than a factor of 1+2^{-n^c} (with respect to the L_{2} norm) is

also NP-hard for randomized reductions. The corresponding decision

problem is NP-complete for randomized reductions.

Revision of: TR97-047

__
TR97-047 | 20th October 1997 00:00
__

#### The Shortest Vector Problem in L_2 is NP-hard for Randomized Reductions.

**Abstract:**
We show that the shortest vector problem in lattices

with L_2 norm is NP-hard for randomized reductions. Moreover we

also show that there is a positive absolute constant c, so that to

find a vector which is longer than the shortest non-zero vector by no

more than a factor of 1+2^{-n^c} (with respect to the L_{2} norm) is

also NP-hard for randomized reductions. The corresponding decision

problem is NP-complete for randomized reductions.