REVIEW 3 major objections 4 minor 13 references
On the Complexity of Combinatorial Optimization on Fixed Structures
T0 review · 3 major / 4 minor · reviewed 2026-08-12 · deepseek-v4-flash
Pith's one-line read This paper proves there are fixed-weight knapsack problems that remain NP-complete.
desk verdict Clever fixed-weight construction, but the printed digit proof doesn't go through; likely repairable, needs a careful fix before it's a theorem. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The central mechanism is constraint aggregation by base-$\beta$ digit separation. The reduction encodes all the 0-1 constraints of the 1-in-3-SAT model into a single linear form $C = \beta^{(2k+1)m} A + C_0$, with each constraint class allocated its own block of digit positions in a large base $\beta$. Because the digit blocks are disjoint, the single pair of inequalities (16) and (23) forces the value of every digit, so each individual equality or inequality constraint must hold. The complementary variables $x_j$ and $\bar{x}_j$, the slack variables $s_{ij}$ and $\bar{s}_{ij}$, and the unique-choice equations $x_j + \bar{x}_j = 1$ and per-clause sums are what allow the constraints to be written in a form amenable to this aggregation.
What would settle it
For the explicit small instance in Section 3.4 (the formula $C_1 \land C_2$ with two clauses and three variables), enumerate all 0-1 assignments to the knapsack variables and check whether the sets of assignments satisfying (16) and (23) coincide with those satisfying the original 1-in-3-SAT constraints; any gap is a direct counterexample to the claimed equivalence.
Extended reading notes
Core claim
The central claim is Theorem 3.8: there exists a computable sequence of tuples $\{a^n\} = \{(a^n_0, a^n_1, \ldots, a^n_n)\}$ such that the FW-Knapsack problem with the constraint defined by $a^n$ in (1) is NP-complete. The proof reduces 1-in-3-SAT to knapsack feasibility. For each pair of numbers of variables and clauses $(k,m)$, the construction fixes the knapsack weights once and for all, so the weights do not depend on the particular CNF formula; only the objective coefficients $c_j$ and the threshold $d$ vary with the formula. Feasibility of the aggregated system is equivalent to the formula having a truth assignment with exactly one true literal per clause. The paper also states that the same reduction adapts to covering feasibility and discusses the constrained shortest-path problem as a motivating example.
Load-bearing premise
The reduction stands or falls on the assumption that the two aggregated inequalities, over disjoint block-digit positions, force every individual constraint of the 1-in-3-SAT model to hold; if some assignment satisfies the aggregate inequalities while violating an original constraint, the equivalence fails.
Editorial extensions
If this is right
- If a fixed computable weight sequence makes FW-Knapsack NP-complete, then no polynomial-time algorithm solves all instances for those weights unless P = NP.
- Preprocessing the weights cannot guarantee a general speedup; any improvement must come from special weight structure, not from the mere fact that weights are fixed.
- The same aggregation reduction can be adapted to prove that the covering feasibility version with fixed constraint coefficients is also NP-complete.
- For weight sequences where the number of maximal feasible subsets is small or the number of distinct subset sums is small, the Section 2 algorithms give polynomial or dynamic-programming upper bounds, so those special fixed structures are genuinely easier.
Reading between the lines
- A natural open question is whether the construction can be strengthened to weight tuples whose coefficients are polynomially bounded in $n$, rather than merely computable; the paper does not address coefficient size.
- The digit-aggregation template is not limited to knapsack: any 0-1 integer program whose constraints have bounded support could be encoded the same way, so the fixed-structure NP-completeness phenomenon likely extends to set packing, covering, and other feasibility problems.
- If the hardness survives in the fixed-weight setting, then the boundary between tractable and intractable fixed structures is a genuine invariant of a problem's combinatorics, not an artefact of input representation.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies the Fixed-Weights Knapsack (FW-Knapsack) problem, where the weight vector and capacity are fixed for each dimension n and only the rewards and reward bound are part of the input. Section 2 gives upper bounds for special fixed-weight families using maximal feasible subsets and a dynamic-programming recurrence over distinct subset sums. Section 3 is the main contribution: a reduction from 1-in-3-SAT to FW-Knapsack via literal variables, occurrence variables, and slack variables, followed by digit-based aggregation of the constraints into two inequalities. The intended conclusion is Theorem 3.8, asserting the existence of a computable fixed-weight sequence for which FW-Knapsack is NP-complete. Section 4 sketches extensions to covering and to constrained shortest path. As printed, the reduction contains missing-overbar sign errors and an incorrect bound in the digit-separation proof, so the central theorem is not currently established, though the construction appears repairable.
Significance. If repaired, the result is significant: it shows that fixing the coefficients in advance does not by itself remove NP-completeness for 0-1 linear feasibility problems. The construction is self-contained, uses only the standard NP-completeness of 1-in-3-SAT, and gives an explicit digit-allocation table for the fixed weights, so there is no circularity or dependence on the authors' prior results. The positive results in Section 2 are elementary but provide a useful contrast. However, because the load-bearing reduction is not fully verified as printed, the significance is conditional on a careful revision.
major comments (3)
- [Section 3.1.3, Eqs. (11) and (12)] As printed, the equations do not enforce the intended inequalities. Eq. (11) is displayed as x_ij + s_ij + x_j = 1. For 0/1 variables this forces x_ij = 0 whenever x_j = 1 and permits x_ij = 1 when x_j = 0, which is the reverse of the intended implication x_j ≥ x_ij; the intended form is x_ij + s_ij = x_j, equivalently x_ij + s_ij + (not x_j) = 1. The same overbar omission affects Eq. (12) and the displays of (9) and (10). With the printed equations, a satisfying assignment with exactly one true literal per clause cannot be lifted to the occurrence variables, so the direction from a satisfying 1-in-3 assignment to a feasible knapsack solution fails, and Proposition 3.7 and Theorem 3.8 are not established. This appears repairable as a notation error, but it is load-bearing and must be corrected and re-verified.
- [Proposition 3.4] The proof relies on the inequality 2km times the sum of beta^i from i=0 to (2k+1)m-1 being strictly less than beta^{(2k+1)m}. This is false for m > 1; with the natural choice beta = p+1 = 2k+1, the left-hand side is asymptotic to m beta^{(2k+1)m}, a factor of m too large. Consequently the contradiction derived from assuming A ≤ b-1 does not follow. The bound should be replaced by a digit-wise upper bound on C0 that accounts for the actual support and coefficients of the aggregated constraints, and the choice of beta must be justified with respect to that bound. As written, Proposition 3.4 is unproved.
- [Section 3.3, dimension indexing] The claim that one may assume k = m 'without loss of generality' is not justified. The reduction sets n = 2k + 4km, which is not injective in (k,m); for example, (1,4) and (3,1) both give n = 18. A single fixed tuple of dimension n cannot serve two different pairs (k,m) with incompatible weight tables. If the intention is to restrict to square instances, the paper must prove that 1-in-3-SAT remains NP-complete under a padding that equalizes the numbers of variables and clauses, or it must use an injective encoding of (k,m) into n. Without this, the existence of the computable sequence in Theorem 3.8 is not fully established.
minor comments (4)
- [Throughout] Overbars are missing in many formula displays, e.g. 'x_i ≥ x_ij' in Section 3.1.3 and the argument lists in (18). This is a presentation issue as well as a technical one; a careful pass with a proper LaTeX build is needed.
- [Abstract] 'a objective function' should be 'an objective function'.
- [Appendix A] In the proof of Proposition 3.3, the first sentence says 'if (x) satisfies (14), then it satisfies (14)'; the second occurrence should be (13).
- [Proposition 3.4] Several exponents are printed with missing parentheses, such as 'beta2k+1)m' and 'beta 2k+1)m'; these should be beta^{(2k+1)m}.
Circularity Check
No circularity: the fixed-weights knapsack hardness proof is a self-contained reduction from 1-in-3-SAT.
full rationale
The paper's central theorem is obtained by constructing, for each pair (k, m), an explicit fixed weight tuple and capacity, then reducing 1-in-3-SAT to feasibility of two aggregate inequalities. The source problem's NP-completeness is cited to Schaefer and to a Wikipedia sketch, with an independent appendix reduction; no load-bearing assumption is imported from the author's own prior work. The reduction uses standard digit-separation and base-β aggregation (Proposition 3.3, proved in Appendix A), and every gadget variable and coefficient is explicitly defined. There is no fitted parameter, no quantity is defined in terms of the target result, and no prediction is made from data. The only self-reference is the introductory mention of the constrained shortest-path problem (1977), which is not used in the proof of Theorem 3.8. Even if the digit bounds or sign conventions in the written reduction were incorrect, that would be a soundness defect, not circularity. Hence no circular step is identifiable.
Assumptions & free parameters
assumptions (3)
- standard math 1-in-3-SAT is NP-complete
- domain assumption Instances of 1-in-3-SAT can be padded so that the number of variables equals the number of clauses (k=m) without loss of NP-completeness
- domain assumption The integers β = 2k+1 and the aggregated target d are representable in polynomial-size binary encodings, so the reduction runs in polynomial time
Cite this review
Pith. "Pith review of On the Complexity of Combinatorial Optimization on Fixed Structures." pith.science (2026). https://pith.science/paper/2PNZWXCR
@misc{pith2026241116963,
author = {Pith},
title = {Pith review of: On the Complexity of Combinatorial Optimization on Fixed Structures},
year = {2026},
howpublished = {\url{https://pith.science/paper/2PNZWXCR}},
note = {Machine review of arXiv:2411.16963}
}
read the original abstract
Combinatorial optimization can be described as the problem of finding a feasible subset that maximizes a objective function. The paper discusses combinatorial optimization problems, where for each dimension the set of feasible subsets is fixed. It is demonstrated that in some cases fixing the structure makes the problem easier, whereas in general the problem remains NP-complete.
Figures
Reference graph
Works this paper leans on
-
[1]
G. H. Bradley. Transformation of integer programs to knapsack problems. Discrete mathe- matics, 1(1):29–45, 1971
work page 1971
- [2]
-
[3]
M. R. Garey and D. S. Johnson. Computers and intractability , volume 174. freeman San Francisco, 1979
work page 1979
-
[4]
R. M. Karp. Reductibility among combinatorial problems. Complexity of computer compu- tations, 1(1):85–103, 1972
work page 1972
-
[5]
T. J. Schaefer. The complexity of satisfiability problems. In Proceedings of the tenth annual ACM symposium on Theory of computing , pages 216–226, 1978
work page 1978
-
[6]
Boolean Satisfiability Problem. Wikipedia article retrieved October 27, 2024, https://en.wikipedia.org/wiki/Boolean satisfiability problem#Exactly-1 3-satisfiability. Appendix A Proof of Proposition 3.3. Obviously, if (x1, . . . , xn) satisfies (14), then it satisfies (14). Conversely, suppose (x1, . . . , xn) satisfies (14). We first prove (13) for i = m...
work page 2024
-
[7]
( x, y, z) = (1, 0, 0). The system reduces to a + b = 1 b + c = 1 c + d = 0 (26) and the solution is ( a, b, c, d) = (0, 1, 0, 0)
-
[8]
( x, y, z) = (0, 1, 0). The system reduces to a + b = 0 b + c = 0 c + d = 0 (27) and the solution is ( a, b, c, d) = (0, 0, 0, 0)
Show all 13 references
-
[9]
a + b = 0 b + c = 1 c + d = 1 (28) and the solution is ( a, b, c, d) = (0, 0, 1, 0)
( x, y, z) = (0, 0, 1). a + b = 0 b + c = 1 c + d = 1 (28) and the solution is ( a, b, c, d) = (0, 0, 1, 0)
-
[10]
The system reduces to a + b = 1 b + c = 0 c + d = 0 (29) and the solution is ( a, b, c, d) = (1, 0, 0, 0)
( x, y, z) = (1, 1, 0). The system reduces to a + b = 1 b + c = 0 c + d = 0 (29) and the solution is ( a, b, c, d) = (1, 0, 0, 0)
-
[11]
The system reduces to a + b = 1 b + c = 1 c + d = 1 (30) and the solutions are ( a, b, c, d) = (1, 0, 1, 0) and ( a, b, c, d) = (0, 1, 0, 1)
( x, y, z) = (1, 0, 1). The system reduces to a + b = 1 b + c = 1 c + d = 1 (30) and the solutions are ( a, b, c, d) = (1, 0, 1, 0) and ( a, b, c, d) = (0, 1, 0, 1)
-
[12]
The system reduces to a + b = 0 b + c = 0 c + d = 1 (31) and the solution is ( a, b, c, d) = (0, 0, 0, 1)
( x, y, z) = (0, 1, 1). The system reduces to a + b = 0 b + c = 0 c + d = 1 (31) and the solution is ( a, b, c, d) = (0, 0, 0, 1). 16
-
[13]
The system reduces to a + b = 1 b + c = 0 c + d = 1 (32) and the solution is ( a, b, c, d) = (1, 0, 0, 1)
( x, y, z) = (1, 1, 1). The system reduces to a + b = 1 b + c = 0 c + d = 1 (32) and the solution is ( a, b, c, d) = (1, 0, 0, 1). Corollary 4.2. A disjunction x∨y ∨z is true if and only if the following conjunction is satisfiable with exactly one true literal per clause: (¬x ...
Reviewed August 12, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.