ECCC-Report TR97-047https://eccc.weizmann.ac.il/report/1997/047Comments and Revisions published for TR97-047en-usTue, 11 Nov 1997 00:00:00 +0200
Revision 1
| The Shortest Vector Problem in L_2 is NP-hard for Randomized Reductions. |
Miklos Ajtai
https://eccc.weizmann.ac.il/report/1997/047#revision1We 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
Tue, 11 Nov 1997 00:00:00 +0200https://eccc.weizmann.ac.il/report/1997/047#revision1
Paper TR97-047
| The Shortest Vector Problem in L_2 is NP-hard for Randomized Reductions. |
Miklos Ajtai
https://eccc.weizmann.ac.il/report/1997/047We 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.
Tue, 21 Oct 1997 09:51:39 +0200https://eccc.weizmann.ac.il/report/1997/047