2
$\begingroup$

I have a following question about the generalized Bezout’s identity in number theory.

If $gcd(a_1, a_2, …, a_n) = d$, then there are integers $x_1, x_2, …, x_n \in \mathbb{Z}$ such that

$d = a_1x_1 + a_2x_2 + … + a_nx_n$ (1)

has the following properties:

  1. $d$ is the smallest positive integer of this form
  2. every number of this form is a multiple of $d$

my question is can we modify the generalized Bezout’s identity to come up similar expression but instead of $x_i \in \mathbb{Z}$ to be $x_i \in \{\pm 1\}$ antipodal alphabet? In short is there a polynomial time function $f(a_1, a_2, …, a_n)$ that outputs true or false depending if eq(1) has a solution with $x_1, x_2, …, x_n \in \pm 1$ or not?

$\endgroup$
2
  • $\begingroup$ It seems unlikely to arrive at the greatest common divisor of positive numbers by only additions, without subtractions. I.e. the $x_i$'s should be integers instead of natural numbers in Bezout's identity. $\endgroup$
    – Berci
    Jul 20, 2018 at 20:08
  • $\begingroup$ Yes, you are right, I have modified the original question, it needs to be integers. $\endgroup$
    – SpiderMath
    Jul 20, 2018 at 21:17

2 Answers 2

2
$\begingroup$

Whether or not such a sequence $(x_i) \in \{\pm 1\}^n$ exists is an NP-complete problem. That it is in NP is clear. To show that it is also NP-hard, we will reduce the subset sum problem to it.

The subset-sum problem asks, given a sequence $(a_1, \ldots, a_n)$ of natural numbers, and a number $k$, is there a subsequence of the original sequence which adds up to $k$. Rephrasing it in language similar to your problem, it asks if there are $y_i \in \{0, 1\}$ such that $$ y_1a_1 + \cdots y_na_n = k. $$ Now clearly this equation is satisfied if and only if the equation $$ (2y_1 - 1)a_1 + \cdots (2y_n - 1)a_n = 2k - (a_1 + \cdots + a_n) $$ is satisfied -- but this is an instance of your problem, with $x_i = 2y_i - 1$.

Hence, no such polynomial-time algorithm exists unless P = NP.

$\endgroup$
2
  • $\begingroup$ Thanks Mees de Vries for your answer. I agree with you that it is the subset-sum problem which is NP-hard. There must exist some approximation polynomial time algorithm? This problem can be also converted to (1,0) integer linear programming. I have read before that there is a polynomial time algorithm (1,0) integer linear programming for some special case, ...maybe with some constraints? $\endgroup$
    – SpiderMath
    Jul 20, 2018 at 21:37
  • $\begingroup$ Here is the paper I am talking about Journal of Combinatorial Optimization November 2006, Volume 12, Issue 3, pp 187–215 Polynomially solvable cases of the constant rank unconstrained quadratic 0-1 programming problem another paper cedric.cnam.fr/~bentzc/INITREC/Files/CB36.pdf $\endgroup$
    – SpiderMath
    Jul 20, 2018 at 22:00
0
$\begingroup$

One can also say that the complexity of the decision whether eq(1) has a solution or not is the same as solving the eq(1) where the coefficients are $x_i \in \{\pm 1\}$ for $1 \leq i \leq n$. In other words, to find the decision if and only if you solve eq(1)?

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .