{"id":"4f826d78-b6fd-488d-aa80-1ae3863c21d9","arxiv_id":"2411.16963","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"There exists a fixed, computable sequence of knapsack weights such that the feasibility problem, whose input is only the profit vector and target, remains NP-complete.","lead":"This paper studies optimization problems where the 'weights' in a knapsack are fixed in advance for each problem size. It proves that even with fixed weights, the problem can remain NP-complete, while some special structures are easy.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"As printed, equations (11)–(12) force the occurrence variables to be 0 whenever the corresponding literal is true, so Proposition 3.2's 'only if' direction fails and the reduction from 1-in-3-SAT collapses.","rationale":"The manuscript's central claim is that some fixed weight sequence makes knapsack feasibility NP-complete, proved by a reduction from 1-in-3-SAT. For that reduction to work, the auxiliary occurrence variables must satisfy x_ij = 1 iff literal x_j appears in C_i and x_j = 1; the constraint x_j ≥ x_ij is the core mechanism. The printed constraint (11), x_ij + s_ij + x_j = 1, algebraically forces x_ij + x_j ≤ 1, i.e., x_ij is allowed to be 1 only when x_j = 0. This is exactly the reverse of the needed implication, and it makes the 'only if' direction of Proposition 3.2 false: a satisfying assignment cannot be lifted to the auxiliary variables because the clause-sum (4) would be 0 at every clause whose sole true literal is not complemented. The small concrete example in the concrete_test field demonstrates the collapse. Since Theorem 3.8 is proved by composing Proposition 3.2 with Proposition 3.3 and the digit-separation argument, this single sign error breaks the chain. It is almost certainly a dropped overbar in the source rather than a conceptual flaw, and the reader's conditional verdict is the right disposition: the paper should not be accepted until equations (11)–(12) (and the matching overbars in (9)–(10)) are corrected and the digit-separation bounds are re-verified. I also note that the bound in Proposition 3.4 with the printed '2km' factor is not obviously true and should be rechecked, but that is secondary because the sign error already invalidates the proof as written. The reader identified the same weakness, so our assessment agrees.","tokens_in":8723,"tokens_out":13192,"duration_ms":114247,"concrete_test":"Independent check: replace the overbars. (i) Verify that the intended encoding of x_j ≥ x_ij is x_ij + s_ij + x̄_j = 1, not (11) as printed. (ii) Instantiate the printed system on the satisfiable instance C1 = x1∨x2∨x3 with x1=1, x2=x3=0: (11) for (i,j)=(1,1) reads x_11+s_11+1=1, forcing x_11=s_11=0; then (4) for i=1 has sum 0, so no 0/1 solution exists. (iii) Re-run the reduction with (11)–(12) corrected (and the corresponding overbars in (9)–(10)) and verify that the digit-separation proof in Proposition 3.6 and the bound in Proposition 3.4 go through with beta = p+1. If the corrected system reproduces the intended 'only if' direction and the digit bounds, the failure is a typo; otherwise the reduction is structurally invalid.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central reduction depends on the auxiliary constraints (11)–(12) to encode x_j ≥ x_ij and x̄_j ≥ x̄_ij. As printed, (11) is x_ij + s_ij + x_j = 1, which forces x_ij + x_j ≤ 1, i.e., whenever the literal x_j is true, the occurrence variable x_ij must be 0. This is the opposite of the intended implication. Combined with the clause constraint (4) (Σ_j x_ij + Σ_j x̄_ij = 1), this makes the 'only if' direction of Proposition 3.2 fail: for any satisfiable 1-in-3-SAT formula with a true literal in a clause, every occurrence variable that could witness that literal is forced to 0, so the clause sum is 0. Concretely, with C1 = x1∨x2∨x3 and assignment x1=1, x2=x3=0, the printed system has no feasible 0/1 solution even though the formula is satisfiable. The same overbar omission affects (12) and likely (9)–(10). Thus the reduction does not encode 1-in-3-SAT as written; Proposition 3.2, Proposition 3.7 and Theorem 3.8 are not established by the manuscript. The secondary bound issue in Proposition 3.4 (the coefficient '2km' in the digit bound) is also unverified, but the sign error is independently fatal if not typo-corrected.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":8952,"tokens_out":15536,"duration_ms":137758,"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":[{"comment":"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.","section":"Section 3.1.3, Eqs. (11) and (12)"},{"comment":"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":"Proposition 3.4"},{"comment":"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.","section":"Section 3.3, dimension indexing"}],"minor_comments":[{"comment":"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.","section":"Throughout"},{"comment":"'a objective function' should be 'an objective function'.","section":"Abstract"},{"comment":"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).","section":"Appendix A"},{"comment":"Several exponents are printed with missing parentheses, such as 'beta2k+1)m' and 'beta 2k+1)m'; these should be beta^{(2k+1)m}.","section":"Proposition 3.4"}],"recommendation":"major_revision","confidential_remarks":"The main idea is plausible and the errors look repairable, but the printed proof does not currently establish the central theorem. I recommend major revision rather than rejection. The novelty is moderate and the positive results in Section 2 are elementary, but the fixed-weight NP-completeness construction, once corrected, would be a legitimate contribution."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here's my take. The central idea is genuinely clever: build a single fixed weight sequence so that knapsack feasibility with those weights is NP-complete, by encoding the formula only in the profit vector. As far as I know that's new, and the auxiliary-variable design with digit aggregation is non-routine. The paper gets real credit for that.\n\nBut as printed, the proof doesn't go through. The load-bearing problem is equations (11) and (12). Equation (11) reads x_ij + s_ij + x_j = 1, which forces x_ij + x_j ≤ 1. That's the wrong direction: the whole point is to enforce x_j ≥ x_ij, i.e., if the occurrence variable is 1 then the corresponding literal is true. With the equation as written, a true literal forces its occurrence variables to 0, so the clause constraint (4) cannot be satisfied for any clause containing that literal. The 'only if' direction of Proposition 3.2 fails, and with it Propositions 3.6-3.8. This looks like dropped overbars rather than a conceptual mistake—the intended equation should use the complement of the literal—but the manuscript as it stands doesn't encode 1-in-3-SAT.\n\nThere's a second, less fatal issue: in Proposition 3.4 the bound '2km Σ β^i < β^{(2k+1)m}' is false for m > 1 when β = 2k+1. The digit bound needs reworking, but that one is probably fixable by choosing a larger base or spacing positions differently.\n\nThe earlier sections on maximal feasible subsets and dynamic programming are fine, mostly standard but useful framing. The Appendix's proof of NP-completeness of 1-in-3-SAT is a standard gadget argument, nothing wrong there. Citation pattern is clean; no self-citation problems.\n\nWho is this for? Complexity theorists interested in non-uniform, fixed-structure problems and in knapsack-style aggregations. The idea is worth knowing even if this version isn't publishable as-is. I'd send it to a knowledgeable referee—the repair is plausibly a few lines, and a referee can confirm whether the overbar fix and the digit bound actually work. But I would not accept it in this form.","headline":"Clever fixed-weight construction, but the printed digit proof doesn't go through; likely repairable, needs a careful fix before it's a theorem.","tokens_in":9527,"tokens_out":4222,"would_cite":false,"duration_ms":32463,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q17","68Q25","90C27"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper proves there are fixed-weight knapsack problems that remain NP-complete.","keywords":["fixed-weights knapsack","NP-completeness","1-in-3-SAT","constraint aggregation","subset sum","combinatorial optimization","fixed structures","dynamic programming"],"falsifier":"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.","tokens_in":8445,"feed_emoji":"🎒","tokens_out":6723,"duration_ms":60653,"temperature":0.7,"pith_summary":"Knapsack feasibility asks whether some 0-1 choice of items fits under a capacity while meeting a reward threshold. This paper asks what happens when the weights are fixed in advance for every problem size, so that the input consists only of rewards and thresholds. It shows some fixed-weight cases are genuinely easier: if all weights are equal, or if the number of maximal feasible subsets grows slowly, then polynomial or fast dynamic-programming algorithms exist. The main result goes the other way: the paper constructs a computable sequence of fixed weight tuples for which the Fixed-Weights Knapsack Feasibility problem is NP-complete. In other words, knowing the weights in advance is not, in general, enough to make the problem tractable, and the boundary between easy and hard fixed structures is a real mathematical phenomenon.","feed_headline":"Knapsack stays NP-complete even with fixed weights","feed_subtitle":"For some computable weight sequences, preprocessing the weights cannot make knapsack feasibility tractable.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the method of transforming integer programs to knapsack problems, used in Proposition 3.3 to aggregate the equalities.","marker":"[1]"},{"why":"Gives the classic NP-completeness of knapsack and subset-sum that motivates the fixed-weights question and sets the hardness baseline.","marker":"[4]"},{"why":"Establishes the NP-completeness of 1-in-3-SAT, the source problem for the reduction.","marker":"[5]"},{"why":"Provides the exact-1-in-3-satisfiability formulation and proof sketch that the reduction explicitly relies on.","marker":"[6]"}],"fun_headline_variants":["Fixed weights don't make knapsack tractable","NP-complete even when knapsack weights are fixed","Knapsack remains NP-hard for computable weight sequences","Even fixed constraints keep knapsack NP-complete","Preprocessing weights can't fix knapsack hardness"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Fixed weights don't make knapsack tractable","NP-complete even when knapsack weights are fixed","Knapsack remains NP-hard for computable weight sequences","Even fixed constraints keep knapsack NP-complete","Preprocessing weights can't fix knapsack hardness"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000202,"raw_usage":{"total_tokens":1291,"prompt_tokens":763,"completion_tokens":528,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":379,"completion_tokens_details":{"reasoning_tokens":464}},"tokens_in":379,"tokens_out":528,"duration_ms":5456,"temperature":1.0,"reasoning_tokens":464,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T12:47:59.491131+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the method of transforming integer programs to knapsack problems, used in Proposition 3.3 to aggregate the equalities."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Gives the classic NP-completeness of knapsack and subset-sum that motivates the fixed-weights question and sets the hardness baseline."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Establishes the NP-completeness of 1-in-3-SAT, the source problem for the reduction."},{"cited_title":"Wikipedia article retrieved October 27, 2024, https://en.wikipedia.org/wiki/Boolean satisfiability problem#Exactly-1 3-satisfiability","cited_arxiv_id":null,"evidence_quote":"Provides the exact-1-in-3-satisfiability formulation and proof sketch that the reduction explicitly relies on."}],"review_version":1}