We conclude that approximating CVP (resp., SVP) within a factor
of **sqrt(n)** is in the intersection of NP and coAM.
Thus, it seems unlikely that approximating these problems
to within a **sqrt(n)** factor is NP-hard.
Previously, for the CVP (resp., SVP) problem, Lagarias et al showed
that the gap problem corresponding to approximating CVP within
**n cdot sqrt(n)** (resp., approximating SVP within **n**)
is in the intersection of NP and coNP.
On the other hand, Arora et al showed that the gap problem
corresponding to approximating CVP
within **exp(sqrt(log n))** is quasi-NP-hard.

Following the publication of our work,
Jin-yi Cai and Ajay Nerurkar (see ``A note on the non-NP-hardness
of approximate lattice problems under general Cook reductions'',
**IPL**, Vol. 76, pages 61-66, 2000) observed that one can remove
the restriction to **smart** reductions.
Let us rephrase their result as folllows.

*Theorem:* Let **Pi**=(**Yes**,**No**) be a promise problem
that satisfies the following three conditions:
(1) the promise problem **Pi** is NP-hard under (general)
Cook-reductions,
(2) the promise problem **Pi** is in coAM, and
(3) the set **No** is in coAM.
Then AM=coAM.

In the paper we consider the promise problems gapCVP and gapSVP. As shown in the paper, the promise problem gapCVP (resp., gapSVP) is in coAM. Obviously, the set of no-instances is in coNP (and thus in coAM). Thus, if the promise problem gapCVP (resp., gapSVP) is NP-hard under (general rather than only smart) Cook-reductions then AM=coAM.

*Proof:*
Let **L** denote the complement set of **No**;
that is, **L** contains both the yes-instances and the instances
that violate the promise of **Pi**.
Recall that by our hypothesis, **Pi** is NP-hard (under Cook-reductions),
**Pi** is in coAM, and **L** is in AM.

Consider the following prover strategy.
The prover invokes the reduction machine answering
all queries according to **L**,
and sends its computation transcript.
In addition, for queries in **L**, the prover invokes the AM-proof
for proving membership in **L**. For queries out of **L**
(i.e., queries in **No**),
the prover invokes the AM-proof for proving membership in
the complement of the promise problem **Pi**.
Recall that the latter proof system is guaranteed to accept
each input in **No** and reject each input in **Yes**.

Completeness: whenever the query is in **Yes** we answered yes
(because **Yes** is a subset of **L**)
and successfuly proved the validity of this answer.
Furthermore, whenever the query is not in **No**
(but is rather in **L**),
we answered yes and successfuly proved the validity of this answer.
(Note that in these cases we invoke the AM-proof for the set **L**.)
On the other hand, whenever the query is in **No** (i.e., out of **L**),
we answered no and successfuly proved the validity of this answer
(via the AM-proof for proving membership in
the complement of the promise problem **Pi**).

Soundness: Suppose a prover tries to cheat.
Then it must supply an computation transcript with a "wrong" answer
to some query. Intuitively, this query should be one that violates the
promise of **Pi**, because otherwise both proof systems are
guaranteed to work. But also in case the query violates the promise
we are OK, because the reduction is resilient to any answer we give
in this case (and so no answer is "wrong" in this case).
Formally, if the query satisfies the **Pi**-promise,
then the prover cannot convince the verifier of a wrong answer (for it).
Thus, the prover is unlikely to provide an accepting computation of
the reduction that uses wrong answers for these queries, and soundness
follows by the validity of the reduction (which holds no matter how
queries that violate the promise are answered).

Indeed, the key point is that violating queries,
which are handled by the presecribed prover as members of **L**,
do not disrrupt the emulation of the reduction.
In the good case (i.e., completeness) violating queries
are treated as yes-instances (which is fine),
whereas in the bad case (i.e., soundness) we don't care about them.
Furthermore, in the good case (i.e., completeness),
using an AM-proof for **L** (rather than for **Pi**)
guarantees that the completeness condition is satisfied. *QED*

- The paper itself, 1998.

Back to either Oded Goldreich's homepage. or general list of papers.