Short Vectors Dimension 2 (SV2)
Category: Formal Languages
Input
Input vectors $a_1, a_2 \in \Z^2$ that are linearly independent over $\Q$, and a rational number $c \geq 1$.
Problem
Find a nonzero vector $x$ such that $|x| \leq c|y|$ for all $y \in M - \{\vec{0}\}$.
Status
Open (von zur Gathen [1]).
Remarks
IntegerGCD is $\NC^1$ reducible to SV2 [1]. For additional remarks about related problems, see Bachem and Kannan [2].