NP-Completeness of deciding the feasibility of Linear Equations over binary- variables with coefficients and constants that are 0, 1, or -1
Posted by Dagwood EngelbergChermakani, Deepak Ponvel
Abstract
We convert, within polynomial-time and sequential processing, NP-Complete Problemsinto a problem of deciding feasibility of a given system S of linear equations with constants and coefficients of binary-variables that are 0, 1, or -1. S is feasible, if and only if, the NP-Completeproblem has a feasible solution. We show separate polynomial-time conversions to S, from the SUBSET-SUM and 3-SAT problems, both of which are NP-Complete. The number of equations and variables in S is bounded by a polynomial function of the size of the NP-Completeproblem, showing that deciding the feasibility of S is strongly-NP-Complete. Wealsoshow how to apply the approach used for the SUBSET-SUM problemtodecidethe feasibility of Integer Linear Programs, as it involves reducing the coefficient-magnitudes of variables to the logarithm of their initial values, though the number of variables and equations are increased.
Pertaining to: Computation, Computational Complexity, Mathematics, NP
2 comments:
F1XATI0N
said...
June 10, 2023 at 3:04 PM
Why is it same as the article written by deepak poonvel, whats the relation i don't understand
F1XATI0N
said...
June 10, 2023 at 3:13 PM
It is you, you are behind LHOHQ