Mixing
Generalized Bezout's Identity with the constraint coefficient of (+1,-1)
Clash Royale CLAN TAG#URR8PPP
up vote
2
down vote
favorite
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 mathbbZ$ such that
$d = a_1x_1 + a_2x_2 + … + a_nx_n$ (1)
has the following properties:
- $d$ is the smallest positive integer of this form
- 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 mathbbZ$ 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?
number-theory
asked Jul 20 at 19:54
SpiderMath
112
add a comment |Â
up vote
2
down vote
favorite
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 mathbbZ$ such that
$d = a_1x_1 + a_2x_2 + … + a_nx_n$ (1)
has the following properties:
- $d$ is the smallest positive integer of this form
- 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 mathbbZ$ 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?
number-theory
asked Jul 20 at 19:54
SpiderMath
112
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.
– Berci
Jul 20 at 20:08
Yes, you are right, I have modified the original question, it needs to be integers.
– SpiderMath
Jul 20 at 21:17
add a comment |Â
up vote
2
down vote
favorite
up vote
2
down vote
favorite
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 mathbbZ$ such that
$d = a_1x_1 + a_2x_2 + … + a_nx_n$ (1)
has the following properties:
- $d$ is the smallest positive integer of this form
- 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 mathbbZ$ 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?
number-theory
asked Jul 20 at 19:54
SpiderMath
112
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 mathbbZ$ such that
$d = a_1x_1 + a_2x_2 + … + a_nx_n$ (1)
has the following properties:
- $d$ is the smallest positive integer of this form
- 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 mathbbZ$ 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?
number-theory
asked Jul 20 at 19:54
SpiderMath
112
edited Jul 20 at 21:16
asked Jul 20 at 19:54
SpiderMath
112
asked Jul 20 at 19:54
SpiderMath
112
asked Jul 20 at 19:54
SpiderMath
112
112
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.
– Berci
Jul 20 at 20:08
Yes, you are right, I have modified the original question, it needs to be integers.
– SpiderMath
Jul 20 at 21:17
add a comment |Â
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.
– Berci
Jul 20 at 20:08
Yes, you are right, I have modified the original question, it needs to be integers.
– SpiderMath
Jul 20 at 21:17
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.
– Berci
Jul 20 at 20:08
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.
– Berci
Jul 20 at 20:08
Yes, you are right, I have modified the original question, it needs to be integers.
– SpiderMath
Jul 20 at 21:17
Yes, you are right, I have modified the original question, it needs to be integers.
– SpiderMath
Jul 20 at 21:17
add a comment |Â
2 Answers
2
active
oldest
votes
up vote
2
down vote
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.
answered Jul 20 at 20:12
Mees de Vries
13.7k12345
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?
– SpiderMath
Jul 20 at 21:37
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
– SpiderMath
Jul 20 at 22:00
add a comment |Â
up vote
0
down vote
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)?
answered Jul 21 at 13:37
SpiderMath
112
add a comment |Â
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
2
down vote
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.
answered Jul 20 at 20:12
Mees de Vries
13.7k12345
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?
– SpiderMath
Jul 20 at 21:37
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
– SpiderMath
Jul 20 at 22:00
add a comment |Â
up vote
2
down vote
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.
answered Jul 20 at 20:12
Mees de Vries
13.7k12345
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?
– SpiderMath
Jul 20 at 21:37
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
– SpiderMath
Jul 20 at 22:00
add a comment |Â
up vote
2
down vote
up vote
2
down vote
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.
answered Jul 20 at 20:12
Mees de Vries
13.7k12345
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.
answered Jul 20 at 20:12
Mees de Vries
13.7k12345
answered Jul 20 at 20:12
Mees de Vries
13.7k12345
answered Jul 20 at 20:12
Mees de Vries
13.7k12345
answered Jul 20 at 20:12
Mees de Vries
13.7k12345
13.7k12345
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?
– SpiderMath
Jul 20 at 21:37
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
– SpiderMath
Jul 20 at 22:00
add a comment |Â
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?
– SpiderMath
Jul 20 at 21:37
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
– SpiderMath
Jul 20 at 22:00
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?
– SpiderMath
Jul 20 at 21:37
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?
– SpiderMath
Jul 20 at 21:37
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
– SpiderMath
Jul 20 at 22:00
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
– SpiderMath
Jul 20 at 22:00
add a comment |Â
up vote
0
down vote
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)?
answered Jul 21 at 13:37
SpiderMath
112
add a comment |Â
up vote
0
down vote
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)?
answered Jul 21 at 13:37
SpiderMath
112
add a comment |Â
up vote
0
down vote
up vote
0
down vote
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)?
answered Jul 21 at 13:37
SpiderMath
112
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)?
answered Jul 21 at 13:37
SpiderMath
112
answered Jul 21 at 13:37
SpiderMath
112
answered Jul 21 at 13:37
SpiderMath
112
answered Jul 21 at 13:37
SpiderMath
112
112
add a comment |Â
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2857974%2fgeneralized-bezouts-identity-with-the-constraint-coefficient-of-1-1%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
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.
– Berci
Jul 20 at 20:08
Yes, you are right, I have modified the original question, it needs to be integers.
– SpiderMath
Jul 20 at 21:17