(made with google gemini pro)Β
The key difference lies in what you're looking for:
SVP (Shortest Vector Problem) is about finding the shortest non-zero vector within the lattice itself. The search is entirely internal to the lattice.
-
CVP (Closest Vector Problem) is about finding the lattice vector that is closest to some external target point that is not necessarily in the lattice.1
Here's a breakdown of why a problem would be classified as one or the other.
## Shortest Vector Problem (SVP) π
The goal of SVP is to find the non-zero lattice vector with the smallest possible length (or norm).
Input: Just a lattice,
.
Question: What is the vector
(where
) that minimizes the length
?
Think of a perfectly planted orchard where each tree is a point in a lattice. SVP is like asking: "What is the shortest distance between any two trees in this orchard?" You are only concerned with the points (trees) that make up the orchard itself.
A problem is likely SVP if it asks you to:
Find the smallest non-zero element of a lattice.
Determine the minimum distance from the origin to any other lattice point.
Find the "most fundamental" or "shortest repeating" vector in a periodic structure.
## Closest Vector Problem (CVP) π―
The goal of CVP is to find the lattice vector that is nearest to a given target vector, which is usually not a point in the lattice.2
Input: A lattice,
, AND a target vector,
.
Question: What is the vector
that minimizes the distance
?
Using the same orchard analogy: CVP is like dropping your keys somewhere in the orchard and asking: "What is the closest tree to where my keys landed?" The location of your keys is the external target vector , and you're trying to find the best lattice point
(tree) near it.
A problem is likely CVP if it asks you to:
Find the lattice point nearest to a given external point.
"Decode" or "round" an arbitrary vector to the closest point in a lattice.
Correct errors in a signal that is known to belong to a lattice code.
## Summary: SVP vs. CVP
| Feature | Shortest Vector Problem (SVP) | Closest Vector Problem (CVP) |
| Main Goal | Find the shortest non-zero vector in the lattice. | Find the lattice vector closest to an external target vector. |
| Input | A lattice |
A lattice |
| Analogy | What's the shortest distance between two trees? | What's the closest tree to my dropped keys? |
| Mathematical Form | Find |
So, if a problem statement only gives you the definition of a lattice and asks for a property internal to it (like its shortest vector), it's SVP. If it gives you a lattice and an external point, asking you to find the nearest lattice member, it's CVP.
---
Excellent question. Given the basis vectors (1,0) and (0,1), you have the simplest possible lattice: the standard integer grid, often written as . All points on this lattice have integer coordinates, like (2, 5), (-1, 0), etc.
Hereβs how to solve SVP and CVP for this specific lattice.
## How to Solve SVP (Shortest Vector Problem)
1. Goal: Find the shortest non-zero vector in the lattice. This is the same as finding the lattice point closest to the origin (0,0), without picking the origin itself.
2. Identify the Vectors: The vectors in your lattice are of the form , where
and
are any integers.
3. Calculate the Length: The length (or norm) of a vector is
. To find the shortest vector, you need to find integers
and
(not both zero) that make this value as small as possible.
4. Find the Minimum:
If you choose
, the length is
.
If you choose
, the length is
.
Any other combination, like
, gives a longer vector:
.
β Solution: The shortest possible non-zero length is 1. There are four vectors that have this length: (1, 0), (-1, 0), (0, 1), and (-1, 0).
## How to Solve CVP (Closest Vector Problem)
1. Goal: Given an external target vector (which is not on the grid), find the lattice point
that is closest to it.
2. Use an Example: Let's say your target vector is .
3. Find the Closest Integers: For the special case of the integer grid , the solution is incredibly simple: just round each component of the target vector to the nearest integer.
The closest integer to 2.8 is 3.
The closest integer to -1.3 is -1.
β
Solution: The closest lattice vector to the target
is
.
In summary, for the simple lattice generated by (1,0) and (0,1):
SVP is solved by picking any of the basis vectors or their negatives, as their length is 1.
CVP is solved by simply rounding the coordinates of your target vector.
Great question! This is where things get more interesting. When the basis vectors are not perpendicular like (1,0) and (0,1), the lattice is "skewed," and our simple intuitions (like rounding) no longer work directly.
Let's break down how to solve SVP and CVP for the lattice generated by the basis vectors and
.
A point is in this lattice if it can be written as
for some integers
and
. For example, if
and
, we get the lattice point
.
## How to Solve SVP (Shortest Vector Problem)
For a 2D lattice, the shortest vector is often one of the basis vectors or the difference between them. You must check these possibilities to find the true shortest one.
1. Goal: Find the shortest non-zero lattice vector.
2. Method: Calculate the lengths of the most likely candidates: ,
, and
.
-
Length of b1β=(1,2):
β£β£b1ββ£β£=12+22β=1+4β=5ββ2.236
-
Length of b2β=(3,1):
β£β£b2ββ£β£=32+12β=9+1β=10ββ3.162
-
Length of b1ββb2β=(1β3,2β1)=(β2,1):
β£β£b1ββb2ββ£β£=(β2)2+12β=4+1β=5ββ2.236
3. Conclusion: The smallest length we found is .
β
Solution: The shortest non-zero length in this lattice is . There are at least four vectors with this length: (1,2), (-1,-2), (-2,1), and (2,-1).
## How to Solve CVP (Closest Vector Problem)
This is the biggest change. You cannot simply round the coordinates of the target vector anymore. Doing so will almost certainly give you a point that isn't on the skewed grid.
The correct method involves a change of basis.
1. Goal: Given a target vector , find the integers
that make the lattice vector
as close to
as possible.
2. Example: Let's use the same target as before, .
3. Step-by-Step Solution:
-
Step 1: Find the "real" coordinates. Instead of integers, we first find the real numbers c1β and c2β that perfectly describe our target vector in terms of the basis.
This gives us a system of two linear equations:
Solving this system (e.g., by substitution or matrix inversion) gives:
c1β=β1.34
c2β=1.38
-
Step 2: Round these new coordinates. Now you round the coordinates from the skewed system (
,
) to the nearest integers.
-
Step 3: Build the lattice vector. Use these rounded integers to find your answer.
β
Solution: The closest lattice vector to the target is
.
Notice that simply rounding (2.8, -1.3) would give (3, -1), which we showed in the thought process isn't even a point in this specific lattice. The change of basis method is essential for skewed lattices.