{"id":"d2da39a9-4d65-432a-97ff-c8c1eb5382d4","arxiv_id":"2506.12080","paper_version":1,"verdict":"REJECT","confidence":"MODERATE","novelty_score":3.0,"correctness_risk":"high","formal_verification":"none","parameter_count":2,"one_line_summary":"The paper asserts, without a valid derivation, that the knapsack problem has a subexponential-superpolynomial lower bound inherited from the author's prior 3D spin-glass Ising model complexity claims.","lead":"A physics preprint claims to pin down the lower bound of computational complexity for knapsack problems by mapping them onto 3D spin-glass Ising models and a so-called absolute minimum core model. The proof rests on unverified prior results by the same author and on an invalid reduction, so the central claim is not supported.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Eq. (20) transfers a lower bound from a nearest-neighbor 3D spin glass to the all-to-all Ising model that the knapsack mapping actually produces; deleting long-range interactions is a relaxation and cannot preserve hardness, so the knapsack lower bound does not follow.","rationale":"The reader's weakest-assumption identification is correct: Eq. (20) is the load-bearing step. The paper's own mapping from knapsack to spin glass, Eqs. (14)-(15), produces an all-to-all SK model; the subsequent truncation to a 3D nearest-neighbor model by removing long-range bonds is a relaxation and cannot be used to prove a lower bound for the original problem. The paper gives no reduction from the 3D EA spin-glass model to the knapsack problem, which would be the needed direction. The relation C(EA) < C(SK) in Eq. (16) is, if true, an ordering of difficulties, not a hardness-preserving reduction, and it is used in the reverse of the required sense. A secondary concern, consistent with the reader's rationale, is that the lower bound for MSGI3D itself is imported from [14,15] and appears to identify the brute-force search cost of a hand-built AMC model with a lower bound; that identification is not proven in this manuscript. The paper has some genuine supporting context (the NP-completeness of 3D Edwards-Anderson models is established in the literature, and the Ising encoding of knapsack in Eq. (14) is a known construction), but these facts do not bridge the gap. The proposed computational or degree-based check would settle the status of Eq. (20) directly. Therefore the reader's REJECT verdict remains unchanged.","tokens_in":18021,"tokens_out":13220,"duration_ms":140863,"concrete_test":"Take one random 0-1 knapsack instance with N=10, wi,ci in [1,30], and Wmax=40. Build the Hamiltonian of Eq. (14), convert it via Eq. (15) to the all-to-all Ising form, and find the exact ground state by brute force. Delete every interaction beyond nearest-neighbor on a 3D cubic lattice, exactly as the proof of Theorem 1 prescribes, and recompute the ground state. If the truncated ground state differs from the knapsack optimum for any instance, the neglect of long-range interactions changes the optimization problem, so the lower bound established for the truncated 3D Edwards-Anderson model cannot be transferred to the knapsack problem. An analytic shortcut: for N+Wmax>7 the coupling graph in Eq. (15) has degree greater than 6 and cannot be embedded in a 3D cubic lattice without deleting bonds, so Eq. (20) fails as stated.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The proof of Theorem 1 rests on Eq. (20): CL(MKP3D) = CL(MSGI3D). The mapping in Eqs. (14)-(15) yields an all-to-all (Sherrington-Kirkpatrick) Ising Hamiltonian with N+Wmax variables, not a 3D nearest-neighbor Edwards-Anderson model. The proof then says the SK model 'can be reduced' to the 3D EA model 'by simplify neglecting the long-range interactions' (Section 3.4). This is the wrong direction for a lower-bound transfer. Dropping bonds is a relaxation: it changes the feasible set and the ground state, and it can only make the instance easier. A lower bound on the relaxed nearest-neighbor model does not transfer to the original all-to-all model; one needs a polynomial-time reduction from hard 3D EA instances into knapsack instances. Eqs. (16)-(17) only assert C(EA) < C(SK), which is an ordering statement, not a reduction, and it is used backwards. Eq. (20) also inherits the unproved inequality Eq. (8) from [14,15], where the brute-force cost CU of the hand-constructed AMC model is declared to be a lower bound; that is an upper bound on one algorithm unless one proves no faster algorithm exists. Thus the central equality is unsupported, and with it Theorem 1.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The manuscript claims to determine a lower bound on the computational complexity of 0-1 knapsack problems, arguing that it is subexponential and superpolynomial. The argument proceeds by mapping the knapsack problem to an all-to-all (Sherrington-Kirkpatrick) Ising model, then reducing that model to a three-dimensional Edwards-Anderson model by deleting long-range interactions, and finally asserting that the lower bound of the 3D spin-glass Ising model transfers to the knapsack problem via Eq. (20). The paper also asserts the existence of an absolute minimum core (AMC) model whose brute-force complexity is declared to be a lower bound, and uses this to claim an NP-intermediate area for knapsack problems.","tokens_in":18373,"tokens_out":2333,"duration_ms":26573,"significance":"If correct, the result would be a striking complexity-theoretic claim: a nontrivial lower bound for a classical NP-complete optimization problem derived from statistical-mechanical reasoning. The paper does cite known NP-completeness results for spin glasses and knapsack, and it attempts to connect physical topology to complexity classes. However, the central derivation is not supported by the arguments presented. The key transfer of a lower bound from a nearest-neighbor model to an all-to-all model proceeds in the wrong direction, and the asserted lower bound itself rests on an unproved inequality from prior work. Since the main claim is load-bearing and appears unsound, the paper does not meet the standards for publication in its current form.","major_comments":[{"comment":"Equation (20) is the central identity: CL(MKP3D) = CL(MSGI3D). But the mapping in Eqs. (14)-(15) produces an all-to-all (Sherrington-Kirkpatrick) Ising Hamiltonian on N+Wmax spin variables, not a 3D nearest-neighbor Edwards-Anderson model. The proof then says the SK model can be reduced to the EA model by 'simplify neglecting the long-range interactions.' This is the wrong direction for a lower-bound transfer: deleting interactions is a relaxation that can only make the problem easier, so a lower bound on the relaxed nearest-neighbor model does not imply a lower bound on the original all-to-all model. To transfer hardness one would need a polynomial-time reduction from hard 3D EA instances to knapsack instances, which is not provided. Equations (16)-(17) only assert an ordering C(EA) < C(SK), which is not a reduction and is used backwards. Thus Theorem 1 does not follow.","section":"Section 3.4, Eq. (20)"},{"comment":"The lower-bound equations (8) and (19) state that the brute-force complexity CU of the AMC model is a lower bound for the full model's complexity. This is asserted with 'It has been proven [14,15]' but no proof is given here or in the supplied manuscript. CU is, by definition, the cost of one particular algorithm (brute-force search); unless it is proven that no faster algorithm exists, CU is an upper bound on that algorithm's cost, not a lower bound for the problem. The entire chain of reasoning inherits this unsupported premise. A rigorous lower bound would require a complexity-theoretic argument, not a declaration that a hand-constructed 'core' model is minimal.","section":"Section 2.3, Eq. (8) and Section 3.4, Eq. (19)"},{"comment":"The claimed complexity classification is stated as CL(MKP3D) in O((1+ε)^N) with ε→0 and ε≠1/N. This expression is not a well-defined complexity class: O((1+ε)^N) for variable ε is meaningless without specifying how ε scales with N, and the assertion that this equals O(2^{N^{2/3}}) is inconsistent. Moreover, the existence of NPI problems and the location of the AMC model 'on the border' are asserted without a proof that the problems under consideration are indeed neither in P nor NP-complete; Ladner's theorem gives NPI problems under P≠NP, but the paper does not establish that the constructed 'incomplete AMC models' are in NP and not in P.","section":"Section 3.4 and Section 3.5"}],"minor_comments":[{"comment":"The abstract mentions 'improved greatly from O(1.3N) to O((1 + ε)N)' but the standard notation for exponential time is O(1.3^N); as written it appears to claim a polynomial improvement. Please clarify.","section":"Abstract and Section 1"},{"comment":"The chain of inequalities in Eq. (10) mixes asymptotic notation with specific functions and does not define the variable P in O(N^P); this should be written with explicit complexity classes or growth rates.","section":"Section 2.4, Eq. (10)"},{"comment":"Definitions 6 and 7 introduce many symbols (MKPall, MKP3D, MKP2D, MAMC,KP3D, etc.) that are used inconsistently; for example, the proof of Theorem 1 sometimes writes CL(MKP3D) and sometimes CL(MSGI3D) without clarifying the relationship between these models beyond Eq. (20).","section":"Section 3.1, Definitions"},{"comment":"Figures 1, 2, 4, 5, 6, and 7 are described but not displayed in the text; their content is essential for interpreting the AMC model and the alleged topological crossings. Please ensure the figures are included and legible.","section":"Figures"}],"recommendation":"reject","confidential_remarks":"The paper's central claim rests on Eq. (20), which transfers a lower bound by deleting interactions from an all-to-all model to a nearest-neighbor model. This is a fundamental error in direction, and it cannot be repaired by minor edits; a completely different proof strategy would be required. Additionally, the paper appears to cite the author's own prior work for unproved lower-bound assertions, and the complexity notation is loose. The fit with physics.gen-ph is plausible, but the technical content is not acceptable as is."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: Theorem 1 does not follow from the paper's own equations. The mapping in Eqs. (14)-(15) sends knapsack to an all-to-all Sherrington-Kirkpatrick Ising model, but Eq. (20) transfers a lower bound from a 3D nearest-neighbor Edwards-Anderson model, after 'neglecting long-range interactions.' That is the wrong direction: deleting bonds is a relaxation, so a lower bound on the relaxed model says nothing about the original hard instance. The equality in Eq. (20) is also inconsistent with Eq. (17), which states CL(EA) < CL(SK). So the proof contradicts itself.\n\nWhat's actually here: a standard knapsack-to-Ising mapping and a clean summary of knapsack complexity background. The mapping itself is correct and well sourced. The phase diagram with an NPI region is a reasonable visual heuristic, but it is not derived from any new computation.\n\nThe soft spots are load-bearing. The lower bound CU(MAMC,SGI3D) from the author's earlier work is the brute-force cost of a hand-constructed 'absolute minimum core' model. Without a proof that no faster algorithm exists, that is an upper bound on one algorithm, not a lower bound for the problem. Eq. (20) simply asserts equality between the knapsack bound and the spin-glass bound, with no independent derivation. The paper provides no code, data, or algorithmic implementation, and the claimed improvement from O(1.3^N) to O((1+epsilon)^N) is not demonstrated anywhere.\n\nIn short, this is not a new result; it is a renaming of the author's prior spin-glass claim, and the transfer step is invalid. The paper is clearly written in parts and the literature review is adequate, but the central argument is self-contradictory. My recommendation: desk reject. The flaw is identifiable from the equations alone, so it does not need referee time. It might serve as a cautionary example of why relaxation arguments fail, but not as a serious contribution.","headline":"Knapsack lower-bound paper recycles the author's prior spin-glass claim via an invalid relaxation, so the central theorem does not follow.","tokens_in":652,"tokens_out":661,"would_cite":false,"duration_ms":42909,"reading_group":"no","serious_thinker":"no","would_accept_peer_review":false},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["82B20","82B44","68Q17","68Q15"],"pacs":[],"model":"deepseek-v4-flash","headline":"The knapsack problem's lower bound is subexponential and superpolynomial.","keywords":["computational complexity","knapsack problem","spin-glass Ising model","NP-complete","NP-intermediate","absolute minimum core","topology"],"falsifier":"For a small instance, encode the knapsack Hamiltonian (14), solve its all-to-all ground state exactly, then solve the ground state of the truncated six-neighbor 3D lattice obtained by neglecting long-range couplings; any instance where the optimal assignment differs refutes the equality in Eq (20).","tokens_in":17738,"feed_emoji":"🎒","tokens_out":10347,"duration_ms":92313,"temperature":0.7,"pith_summary":"This paper argues that the 0-1 knapsack problem, long known to be NP-complete, has a lower bound on computational complexity that is subexponential and superpolynomial—not polynomial, but not full exponential. The route runs through physics: the knapsack decision variables are mapped to Ising spins in an all-to-all spin-glass Hamiltonian, which is then reduced to a 3D nearest-neighbor spin-glass lattice, whose lower bound the author takes from prior work. If correct, exact solvers could in principle approach $O((1+\\varepsilon)^N)$ with $\\varepsilon \\to 0$, a large improvement over the $O(1.3^N)$ brute-force scale, and the same bound would transfer to other NP-complete problems. The load-bearing step is an equality between the knapsack lower bound and the 3D spin-glass lower bound.","feed_headline":"Knapsack's hardness floor falls between polynomial and exponential","feed_subtitle":"If the spin-glass mapping holds, exact knapsack solvers could run far below brute force.","key_machinery":"The load-bearing object is the absolute minimum core (AMC) model, a minimal two-layer grid of spins with nearest-neighbor interactions and frustrations that is supposed to retain the full hardness of the 3D spin-glass Ising model. Its brute-force cost $C_U(M_{AMC,SGI}^{3D})$ is identified with the lower bound $C_L(M_{SGI}^{3D})$, and Eq (20) asserts the same core model bounds the knapsack problem: $C_L(M_{KP}^{3D}) = C_L(M_{SGI}^{3D})$. The transfer-matrix representation supplies the topological reason: a 3D lattice mapped onto 2D transfer matrices produces crossings and interaction terms $s'_j s'_{j+mn}$ that act as long-range entanglements, and the AMC is the smallest arrangement that keeps those entanglements.","core_discovery":"The paper's central claim is Theorem 1: the lower bound of the computational complexity of the 0-1 knapsack problem on a 3D lattice, $C_L(M_{KP}^{3D})$, is subexponential and superpolynomial. Concretely, the author derives $C_L(M_{KP}^{3D}) \\geq C_U(M_{AMC,KP}^{3D})$, and via Eq (20) sets this equal to the 3D spin-glass Ising lower bound $C_L(M_{SGI}^{3D})$, which is $O(2^{N^{2/3}})=O((1+\\varepsilon)^N)$ with $\\varepsilon \\to 0$ and $\\varepsilon \\neq 1/N$. The same argument places an NP-intermediate (NPI) region between NP-complete and P for knapsack, with the absolute minimum core (AMC) model on the border, meaning the core cannot collapse directly into P.","pith_inferences":["A direct test of the truncation step on small instances would show whether the all-to-all knapsack Hamiltonian and the six-neighbor 3D lattice share the same ground states; if not, the stated lower bound belongs only to the truncated model, not to the original knapsack problem.","Taken literally, the phase diagram implies every NP-complete problem has a hardness core of size $N^{2/3}$, suggesting a general design principle: identify and brute-force the core, then layer the rest.","The promised speedup from $O(1.3^N)$ to $O((1+\\varepsilon)^N)$ is a concrete, benchmarkable claim; comparing the proposed layered algorithm against dynamic programming on difficult knapsack instances would quantify how close the strategy comes to the bound."],"forward_implications":["Exact algorithms for 0-1 knapsack cannot be polynomial unless the claimed lower bound fails; the best possible running time would be $O((1+\\varepsilon)^N)$ with $\\varepsilon \\to 0$, far below the $O(1.3^N)$ brute-force scale.","The same subexponential, superpolynomial lower-bound class would transfer to other NP-complete problems, including TSP, K-SAT, and neural networks, through the paper's universality argument.","The AMC model becomes a concrete target for algorithm design: solve the two-layer core by brute force and parallelize the remaining layers.","An NP-intermediate area for knapsack exists, with incomplete AMC models playing the role of the classically constructed NP-intermediate problems."],"supporting_citations":[{"why":"Supplies the Hamiltonian (14) that encodes the 0-1 knapsack problem as an all-to-all Ising model, the bridge from knapsack to spin glasses.","marker":"[39]"},{"why":"Defines the all-to-all spin-glass model whose ground-state search is NP-complete; the knapsack Hamiltonian is cast in this form.","marker":"[46,47]"},{"why":"Defines the Edwards-Anderson nearest-neighbor spin-glass model used as the 3D target after truncation.","marker":"[4]"},{"why":"The author's prior result asserting the $O(2^{nm})$ lower bound for the 3D spin-glass model, which Eq (20) transfers to knapsack.","marker":"[14]"},{"why":"The earlier mapping of the 3D spin-glass model to K-SAT problems that established the AMC/NPI framework reused here.","marker":"[15]"},{"why":"The classical construction of NP-intermediate problems, cited as the basis for the NPI region in the phase diagram.","marker":"[36]"},{"why":"Establishes the NP-completeness of knapsack problems and identifies where hard instances lie, grounding the problem being bounded.","marker":"[18,19]"},{"why":"Provides the current $O(1.3^N)$ exact-search benchmark that the paper's proposed algorithm explicitly improves upon.","marker":"[6]"}],"fun_headline_variants":["Knapsack hardness locked between P and NP-complete","Subexponential lower bound proven for knapsack problems","Knapsack solvers can't beat subexponential time","New NPI region found in knapsack complexity landscape","Knapsack's true complexity: superpolynomial, subexponential"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The argument stands or falls on the claim that the knapsack problem's lower bound equals the 3D spin-glass model's lower bound, a claim reached by dropping long-range couplings—and dropping couplings can only make a problem easier, so the truncated model cannot force a lower bound on the original.","fun_headline_variants_meta":{"raw":{"variants":["Knapsack hardness locked between P and NP-complete","Subexponential lower bound proven for knapsack problems","Knapsack solvers can't beat subexponential time","New NPI region found in knapsack complexity landscape","Knapsack's true complexity: superpolynomial, subexponential"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000407,"raw_usage":{"total_tokens":2124,"prompt_tokens":965,"completion_tokens":1159,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":581,"completion_tokens_details":{"reasoning_tokens":1074}},"tokens_in":581,"tokens_out":1159,"duration_ms":8974,"temperature":1.0,"reasoning_tokens":1074,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T05:44:58.586665+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"For a small instance, encode the knapsack Hamiltonian (14), solve its all-to-all ground state exactly, then solve the ground state of the truncated six-neighbor 3D lattice obtained by neglecting long-range couplings; any instance where the optimal assignment differs refutes the equality in Eq (20).","supporting_citations":[{"cited_title":"Kyriienko, H","cited_arxiv_id":null,"evidence_quote":"Supplies the Hamiltonian (14) that encodes the 0-1 knapsack problem as an all-to-all Ising model, the bridge from knapsack to spin glasses."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"The author's prior result asserting the $O(2^{nm})$ lower bound for the 3D spin-glass model, which Eq (20) transfers to knapsack."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"The earlier mapping of the 3D spin-glass model to K-SAT problems that established the AMC/NPI framework reused here."},{"cited_title":"Ladner, On the structure of polynomial time r educibility, J","cited_arxiv_id":null,"evidence_quote":"The classical construction of NP-intermediate problems, cited as the basis for the NPI region in the phase diagram."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the current $O(1.3^N)$ exact-search benchmark that the paper's proposed algorithm explicitly improves upon."}],"review_version":1}