Question

Consider a variant of linear programming where in addition to original linear constraints, we are also allowed to have constraints of the form ∣a

1 x 1 +…+a n x n ∣=b where a 1 ,…,a n ,b are numbers, and x 1 ,…,x n are variables. Let us call such a program, an Absolutevalue Program. For example, the following is an Absolute-value Program.
max3x−4y+z+3w
s.t. 5x−z+3w≤6
2x−y+2w≥−7
∣x+y−2w∣=3
∣x+5y−w∣=10
y≥0
z≤0
w≥0
Prove that Absolute-value Programming is NP-complete. More precisely, prove that the following problem is NP-complete: - Input: A maximization Absolute-value Program and an integer k. - Question: Does the optimal solution to the program have cost at least k ?

Answer 1

Absolute-value Programming is NP-complete because a candidate solution can be verified in polynomial time and any NP problem can be reduced to it, such as by demonstrating a reduction from the NP-complete Subset Sum problem.

Step-by-step explanation:

To prove that Absolute-value Programming is NP-complete, one must establish two main points: that it belongs to the NP class, and that every problem in NP can be reduced to it in polynomial time. Firstly, a candidate solution to an Absolute-value Program can be verified in polynomial time. If we are given a possible solution set of variables, we can plug in these values and check whether all the constraints, including the absolute value equations, are satisfied and if the objective function value is at least k.

Showing that Absolute-value Programming is NP-hard typically involves reducing a known NP-complete problem to it. One classic NP-complete problem is the Subset Sum problem, where we are given a set of integers and are asked if there exists a subset of them that adds up to another given integer. We can reduce Subset Sum to an Absolute-value Program by creating variables that represent the inclusion of elements in the subset. The sum of these variables, accounting for whether they are included in the subset (represented as 1) or not (represented as 0), and an absolute value constraint set to the target sum would construct an equivalent Absolute-value Programming instance.

Since verifying the solution is doable in polynomial time and we can reduce a known NP-complete problem to it in polynomial time, we can conclude that Absolute-value Programming is indeed NP-complete. This complexity status indicates that finding an optimal solution to such programs is, based on current knowledge, computationally intractable for large instances.