2
$\begingroup$

My question is related to the Integer Relation Detection Problem which can be formulated as:

$a_1x_1 + a_2x_2 + \cdots + a_nx_n = 0$

Where $\forall_{a_i} a_i\in\mathbb{Z},a_i and $\exists_{a_i} a_i\neq 0$, and $\forall_{x_i} x\in \mathbb{R}$. $c$ and vector $\mathbf{x}$ are given, and the problem is to find a valid vector $\mathbf{a}$ that satisfies these constraints.

There are a few algorithms to solve this problem, listed on the wikipedia page linked.

My question: are there algorithms for a solution to the same problem with the modification that:

$a_1x_1 + a_2x_2 + \cdots + a_nx_n = 1$

Or equivalently (I believe):

$a_1x_1 + a_2x_2 + \cdots + a_nx_n = b$

$b\in \mathbb R$ is a given.

I would love to see some reduction to an existing problem with a polynomial-time algorithm, such as Integer Relation Detection, or Simultaneous Integer Relation Detection. Another possibility is that this is a hard problem.

2 Answers 2