<p>Let's assume that you can compare the lengths of two vectors in polytime.</p>

<p>If your problems are NP-complete then NP=co-NP, which is thought to be unlikely. </p>

<p>This follows because the problem belongs to co-NP (a shorter vector provides a certificate that the original vector is not the shortest). It is known that if any NP-complete problem belongs to co-NP, then NP=co-NP. (For example, see <a href="http://en.wikipedia.org/wiki/Co-NP" rel="nofollow">the wiki page on co-NP</a>.)</p>

CC BY-SA 3.0
2013-09-26T02:33:03.453Z
"then you can provide a shorter vector".... I do not think this is easy. This can solve the SVP itself. Just take a vector with a bound B. If you dont have one, find one in bound 2B and so on. If the vector is not shortest, as you are saying, find a smaller one and keep ddoing this and you will hit at least a close approx to SVP.
Turbo
CC BY-SA 3.0
2013-09-26T02:34:16.070Z
I didn't mean to say that you can actually find the shorter vector quickly, just that if one is provided that you can check it quickly.
Austin Buchanan
CC BY-SA 3.0
2013-09-26T02:36:35.737Z
no, no no. You give me vector X and ask me if it is the shortest. I respond by saying "No, X is not the shortest vector, because I have a vector Y that is shorter."
Austin Buchanan
CC BY-SA 3.0
2013-09-26T02:37:48.400Z
How will you find Y? This is the certificate for no instance. This has to be in P for the problem to be in CoNP. If Y cannot be found in polytime, then the problem is not in CoNP. Isn't it? That is what I am saying.
Turbo
CC BY-SA 3.0
2013-09-26T02:40:34.270Z
"In simple terms, co-NP is the class of problems for which efficiently verifiable proofs of no instances, sometimes called counterexamples, exist."
Austin Buchanan
CC BY-SA 3.0
2013-09-26T02:42:29.250Z
"efficiently verifiable proof of no instance" your proof is Y (the countewr example). Did you get it efficiently? May be this problem is silly. that is why I first posted in cs.stack
Turbo
CC BY-SA 3.0
2013-09-26T02:51:56.780Z
Well also it is known approximating to $\sqrt{n}$ is in $NP \cap CoNP$ but (obviously) not NP hard. So why would exact (not approximate) SVP or CVP be in just in CoNP but not in NP (this case is NP-hard). How does it leave the property of being in NP but stay in Co NP (if what you are saying is right) when we transition from approx SVP/CVP to the exact SVP or CVP problem?
Turbo
CC BY-SA 3.0
2013-09-26T12:04:55.510Z
@JAS you seem to have some basic misunderstanding of what coNP is. The certificate of No-instances only needs to efficiently verifiable, not efficient to compute (if it were then the problem would be in P). For examble, for Tautology the typical certificate is a satisfying assignment, and we don't expect you can find a satisfying assignment efficiently. I think Austin's answer is correct
Sasho Nikolov
CC BY-SA 3.0
2013-09-26T12:25:38.777Z
I see. Thankyou. I originally posted this in cs.stack I was not getting this response I needed.
Turbo
CC BY-SA 3.0
2013-09-26T12:29:41.983Z
This is what confused me. Approx to multiple of $n$ is in $np \cap conp$. Approx to $1$ multiple (which is exact) is only in $conp$. How does the problem evade the property of being in $np$ at stricter approx while remaining in $conp$? Is there a transition zone or a gap?
Turbo
CC BY-SA 3.0
2013-09-26T12:35:59.817Z
when you allow for larger approximation the problem certifying yes-instances becomes easier, and for large enough gaps can be done efficiently; however, when the approximation gap allowed is big enough to make certifying yes instances possible, the problem is naturally "too easy" to be NP-hard. certifying no-instances is always efficiently doable, so both approximate and exact versions are in coNP (there is no "entering coNP zone").
Sasho Nikolov
CC BY-SA 3.0
2013-09-26T12:39:17.077Z
I see. The point is CoNp verification is easy to do.
Turbo
CC BY-SA 3.0
2013-09-26T02:22:30.890Z
2013-09-26T02:57:07.630Z
2013-09-26T02:57:07.630Z
Austin Buchanan
<p>Can there be polynomial time algorithms which can verify if the given vector in the lattice is</p>

<p>1) the shortest?</p>

<p>2) the closest to an arbitrary point?</p>

<p>Both problems are NP-hard. Are there obstructions for them being NP complete?</p>

CC BY-SA 3.0
2013-09-26T01:53:50.570Z
The question is: do these problems belong to NP? They do seem to belong to co-NP.
Austin Buchanan
CC BY-SA 3.0
2013-09-26T02:26:40.720Z
@JAS You posted this on cs.stackexchange and got an answer (then deleted it later). Why are you posting it again here? That aside, what specifically do you mean by "obstructions"?
mdxn
CC BY-SA 3.0
2013-09-26T02:30:28.753Z
@mdx sorry about the anti-climax. your answer was not what I expected. I have mentioned that the problem is NP hard. Your quote was "There can be if and only if they are NP-complete problems. I'll update the answer to better address your question." I already knew that.
Turbo
<np-hardness>
Easy verifier for Shortest Vector
Turbo
# Easy verifier for Shortest Vector

(Asked by: username_0 on 2013-09-26)

Can there be polynomial time algorithms which can verify if the given vector in the lattice is

1) the shortest?

2) the closest to an arbitrary point?

Both problems are NP-hard. Are there obstructions for them being NP complete?

**Tags:** np-hardness
> **Comments:**
> **username_1**: The question is: do these problems belong to NP? They do seem to belong to co-NP.  
> **username_2**: @JAS You posted this on cs.stackexchange and got an answer (then deleted it later). Why are you posting it again here? That aside, what specifically do you mean by "obstructions"?  
> **username_0**: @mdx sorry about the anti-climax. your answer was not what I expected. I have mentioned that the problem is NP hard. Your quote was "There can be if and only if they are NP-complete problems. I'll update the answer to better address your question." I already knew that.  

---

## 1 answers

### Answer by username_1 on 2013-09-26. Score: 1

Let's assume that you can compare the lengths of two vectors in polytime.

If your problems are NP-complete then NP=co-NP, which is thought to be unlikely.

This follows because the problem belongs to co-NP (a shorter vector provides a certificate that the original vector is not the shortest). It is known that if any NP-complete problem belongs to co-NP, then NP=co-NP. (For example, see [the wiki page on co-NP](http://en.wikipedia.org/wiki/Co-NP).)

> **Comments:**
> **username_0**: "then you can provide a shorter vector".... I do not think this is easy. This can solve the SVP itself. Just take a vector with a bound B. If you dont have one, find one in bound 2B and so on. If the vector is not shortest, as you are saying, find a smaller one and keep ddoing this and you will hit at least a close approx to SVP.  
> **username_1**: I didn't mean to say that you can actually find the shorter vector quickly, just that if one is provided that you can check it quickly.  
> **username_1**: no, no no. You give me vector X and ask me if it is the shortest. I respond by saying "No, X is not the shortest vector, because I have a vector Y that is shorter."  
> **username_0**: How will you find Y? This is the certificate for no instance. This has to be in P for the problem to be in CoNP. If Y cannot be found in polytime, then the problem is not in CoNP. Isn't it? That is what I am saying.  
> **username_1**: "In simple terms, co-NP is the class of problems for which efficiently verifiable proofs of no instances, sometimes called counterexamples, exist."  
> **username_0**: "efficiently verifiable proof of no instance" your proof is Y (the countewr example). Did you get it efficiently? May be this problem is silly. that is why I first posted in cs.stack  
> **username_0**: Well also it is known approximating to $\sqrt{n}$ is in $NP \cap CoNP$ but (obviously) not NP hard. So why would exact (not approximate) SVP or CVP be in just in CoNP but not in NP (this case is NP-hard). How does it leave the property of being in NP but stay in Co NP (if what you are saying is right) when we transition from approx SVP/CVP to the exact SVP or CVP problem?  
> **username_3**: @JAS you seem to have some basic misunderstanding of what coNP is. The certificate of No-instances only needs to efficiently verifiable, not efficient to compute (if it were then the problem would be in P). For examble, for Tautology the typical certificate is a satisfying assignment, and we don't expect you can find a satisfying assignment efficiently. I think Austin's answer is correct  
> **username_0**: I see. Thankyou. I originally posted this in cs.stack I was not getting this response I needed.  
> **username_0**: This is what confused me. Approx to multiple of $n$ is in $np \cap conp$. Approx to $1$ multiple (which is exact) is only in $conp$. How does the problem evade the property of being in $np$ at stricter approx while remaining in $conp$? Is there a transition zone or a gap?  
> **username_3**: when you allow for larger approximation the problem certifying yes-instances becomes easier, and for large enough gaps can be done efficiently; however, when the approximation gap allowed is big enough to make certifying yes instances possible, the problem is naturally "too easy" to be NP-hard. certifying no-instances is always efficiently doable, so both approximate and exact versions are in coNP (there is no "entering coNP zone").  
> **username_0**: I see. The point is CoNp verification is easy to do.  

---

