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

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.

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.