<p>This does not imply that SVP is in coNP without a proof that a basis with the necessary properties (all its GS norms are larger than <span class="math-container">$d$</span>) actually exists.</p>

CC BY-SA 4.0
2023-04-19T02:13:31.703Z
2023-04-19T02:13:31.703Z
cbright
<p>From <a href="https://cbright.myweb.cs.uwindsor.ca/reports/cs667proj.pdf" rel="nofollow noreferrer">https://cbright.myweb.cs.uwindsor.ca/reports/cs667proj.pdf</a></p>
<blockquote>
<p>More precisely, the decision version of the poly(n)-unique SVP problem lies in NP and coNP. This means
that given a lattice and a target bound d there is a short certificate which proves that the shortest vector
is either shorter than d or longer than d. In the former case, the certificate is simply the shortest vector
itself. In the latter case, the certificate is a basis of the lattice in which every vector in the Gram–Schmidt
orthogonalization of the basis is longer than d.</p>
</blockquote>
<p>It seems like we can use this logic to deduce that SVP is also in coNP. Since we know that the Gram-Schmidt orthogonalization of the basis gives us a lower bound of the shortest vector.</p>
<p>It seems like we can provide a certificate that is the basis of the lattice and its Gram-Schmidt orthogonalization will be able to answer the no instance of the problem.</p>

<lattice>
Why is SVP not in coNP if Gram Schmidt Orthogonalization can provide us with a lower bound of the shortest vector
bubakazouba
# Why is SVP not in coNP if Gram Schmidt Orthogonalization can provide us with a lower bound of the shortest vector

(Asked by: username_0 on 2023-04-18)

From <https://username_1.myweb.cs.uwindsor.ca/reports/cs667proj.pdf>

> More precisely, the decision version of the poly(n)-unique SVP problem lies in NP and coNP. This means
> that given a lattice and a target bound d there is a short certificate which proves that the shortest vector
> is either shorter than d or longer than d. In the former case, the certificate is simply the shortest vector
> itself. In the latter case, the certificate is a basis of the lattice in which every vector in the Gram–Schmidt
> orthogonalization of the basis is longer than d.

It seems like we can use this logic to deduce that SVP is also in coNP. Since we know that the Gram-Schmidt orthogonalization of the basis gives us a lower bound of the shortest vector.

It seems like we can provide a certificate that is the basis of the lattice and its Gram-Schmidt orthogonalization will be able to answer the no instance of the problem.

**Tags:** lattice


---

## 1 answers

### Answer by username_1 on 2023-04-19. Score: 1 | Accepted answer

This does not imply that SVP is in coNP without a proof that a basis with the necessary properties (all its GS norms are larger than $d$) actually exists.


---

