{"id":"7253fd46-cfb7-4653-aab3-67e2f2d28677","arxiv_id":"2611.16814","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"A deterministic 3-SAT algorithm with running time O(1.32736^n) is given, improving the previous best bound by about 5.7e-5 in the exponential base.","lead":"The paper presents a deterministic algorithm for 3-SAT that runs in O(1.32736^n) time, improving the previous best bound of 1.32793^n. It introduces a technique called 'block expansion' that strengthens constraints from short chains, and provides a weighted analysis to balance branching, partial assignment, and local search costs.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek/deepseek-v4-flash","headline":"The block-margin analysis in Appendix B relies on a finite enumeration of block types whose completeness is not fully argued, and the claimed lower bound on the smallest eigenvalue of the similarity matrix for a block (Lemma 3.5) uses d ≤ 9, which depends on the block-size cap (Lemma B.4) that…","rationale":"The reader's weakest_assumption correctly identifies that the bound on block size (d ≤ 9) is critical and that its proof relies on a finite but complex combinatorial check. The paper's own Lemma B.4 is asserted in a single paragraph without a rigorous derivation, and the subsequent analysis depends on this cap. The reader's verdict of CONDITIONAL is appropriate because the central claim is likely correct but the proof has a gap that should be addressed. My stress-test confirms this: the block-size cap is the most load-bearing concern, and the concrete test I propose would directly address it. I agree with the reader's assessment.","tokens_in":31490,"tokens_out":785,"duration_ms":9366,"concrete_test":"Independently enumerate all possible block types that can arise from the expansion procedure (Algorithm 7) under the stated truncation rule, and verify that each satisfies d ≤ 9. If any block type has d > 9, recompute the smallest eigenvalue of its similarity matrix; if the eigenvalue falls below 2^{-9}, check whether the margin A(B) remains nonnegative under the weaker bound. This test would settle whether the spectral argument in Lemma 3.5 is sound for all blocks the algorithm can produce.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The central claim of a 1.32736^n deterministic 3-SAT algorithm depends on the existence of a feasible characteristic distribution for each block type and the lower bound λ_B ≥ (1+ε)(3/7)^{t(B)}(3/4)^{v(B)} (Lemma 3.5). This bound is derived from a spectral argument that assumes the smallest eigenvalue of the similarity matrix for a block is at least 2^{-9}, which holds because the block size is bounded (d ≤ 9). The bound on block size (d ≤ 9) is asserted in Lemma B.4: \"Every block B ∈ I satisfies #{chains in B} ≤ 5, v(B) ≤ 500, #{defining and center occurrences} ≤ 332.\" The proof of Lemma B.4 is given in a single paragraph that sketches a counting argument but does not provide a rigorous derivation from the algorithm's expansion procedure. The argument assumes that each chain has at most 66 defining occurrences and at most 100 variables, but these bounds themselves depend on the specific truncation rule and the structure of chains produced by the branching algorithm, which are not fully analyzed. Moreover, the paper states that the block cap \"makes the relation library of DLS finite\" and \"is what allows S and H to be computed before either terminal runs,\" but the actual computation of these costs for all possible block types is not demonstrated. If a block could be larger than d=9, the eigenvalue bound would weaken, potentially invalidating the margin calculations that are essential to the proof that A(B) ≥ 0 for all blocks (Lemma 5.8). The paper acknowledges that the characteristic distribution may have negative entries (Appendix A.4: \"its entries need not be nonnegative\"), which would make Liu's equality-based characteristic condition infeasible, but then relies on a weaker lower-bound condition (Lemma A.9) that still requires the eigenvalue bound. The entire edifice of the improved bound rests on this eigenvalue argument, and the block-size cap is not rigorously justified.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek/deepseek-v4-flash","summary":"The paper presents a deterministic algorithm for 3-SAT with running time O(1.32736^n), improving the previous best bound of 1.32793^n by Liu. The algorithm builds on a branching-and-chain framework, augmented with an expansion procedure that joins short chains into blocks, which impose stronger constraints. After branching, the algorithm chooses between derandomized local search (DLS) guided by block structure and enumeration of block assignments together with port variables (PA2), reducing the remaining formula to 2-SAT. A weighted analysis of branching, partial-assignment, and local-search costs establishes the running-time guarantee. The framework is also extended to k-SAT for k≥4, yielding improved bounds.","tokens_in":31979,"tokens_out":2517,"duration_ms":17198,"significance":"If the result holds, it provides the fastest known deterministic algorithm for 3-SAT, improving a bound that has stood for several years. The techniques—chains, blocks, expansion, and the weighted analysis—are novel and may be applicable to other constraint satisfaction problems. The paper also offers a self-contained framework and provides guidance for practical SAT solver design. The improvement is numerically modest but strict, and the approach is promising for further optimization.","major_comments":[{"comment":"The block size cap (d ≤ 9, chains ≤ 5, v(B) ≤ 500, occurrences ≤ 332) is asserted in Lemma B.4 with a brief proof sketch. The proof relies on bounds on chain length (v(S) ≤ 100, defining occurrences ≤ 66) that are not rigorously derived from the branching algorithm's truncation rule. The paper states that these bounds depend on the specific truncation rule and the structure of chains, but the derivation is not provided. If a block could be larger than d=9, the eigenvalue bound in Lemma 3.5 (smallest eigenvalue ≥ 2^{-9}) would weaken, potentially invalidating the margin calculations that are essential to Lemma 5.8. The authors acknowledge that the block cap 'makes the relation library of DLS finite' and 'is what allows S and H to be computed before either terminal runs,' but the actual computation of these costs for all possible block types is not demonstrated. This is a load-bearing issue because the central claim depends on the existence of a feasible characteristic distribution for each block type and the lower bound λ_B ≥ (1+ε)(3/7)^{t(B)}(3/4)^{v(B)} (Lemma 3.5), which assumes d ≤ 9. The paper should provide a rigorous proof of the block size cap or a more detailed argument that the eigenvalue bound holds for all blocks that can actually be produced by the expansion procedure.","section":"Appendix B, Lemma B.4","authors_acknowledge":null,"authors_acknowledge_p":null},{"comment":"The proof that A(B) > 0 for all one-center and two-center blocks relies on a finite enumeration of contact geometries and certified margins. The paper states that 'the finite endpoint checks are collected in Table 3, and every entry is positive,' but Table 3 is not provided in the manuscript (the table is referenced but not included). Without the actual numerical values and the verification that all cases are covered, the proof is incomplete. The authors should include the full table or provide a more systematic argument that does not depend on an omitted table.","section":"Appendix B, Lemma B.2 and B.3","authors_acknowledge":null,"authors_acknowledge_p":null},{"comment":"The proof of Lemma 5.8 (nonnegative margins for all blocks and weak chains) is split between the main text and Appendix B. The main text provides the chain inequality proof using bounds on m_w from Theorem A.6 and Lemmas A.7, A.8. However, the proof that A(B) ≥ 0 for blocks is deferred to Appendix B, which relies on the block size cap and the omitted Table 3. As noted above, the block size cap is not rigorously proven, and the table is missing. Therefore, the proof of Lemma 5.8 is incomplete. The authors should either provide a complete proof of the block size cap and include the missing table, or restructure the argument to avoid reliance on these unverified components.","section":"Section 5.2, Lemma 5.8","authors_acknowledge":null,"authors_acknowledge_p":null},{"comment":"Lemma 3.5 claims a uniform block gain λ_B ≥ (1+ε)(3/7)^{t(B)}(3/4)^{v(B)} with ε = 1/(23·2^16). The proof uses a spectral argument that assumes the smallest eigenvalue of the similarity matrix for a block is at least 2^{-9}, which holds because d ≤ 9. However, the bound d ≤ 9 depends on the block size cap (Lemma B.4), which is not rigorously proven. Additionally, the proof assumes that the block's solution space A is a strict subset of A' = A_0^t × {0,1}^v, but this relies on the existence of a 'witness' clause distinct from every source. The paper should clarify that this witness is the center clause itself, and that the inclusion is strict because the center clause is not satisfied by all assignments in A'. This is a minor point, but the reliance on the unproven block size cap is a major concern.","section":"Section 3.2, Lemma 3.5","authors_acknowledge":null,"authors_acknowledge_p":null},{"comment":"The generalization to k≥4 is presented as a recurrence that depends on the 3-SAT base case c_3 = 1.3273599467... from Theorem 5.10. However, the proof of Theorem 5.10 itself depends on the unverified block size cap and the missing Table 3. Therefore, the entire generalization is contingent on the correctness of the 3-SAT analysis. The authors should either provide a complete proof for the 3-SAT case or state that the k≥4 results are conditional on the 3-SAT analysis.","section":"Section 6, Theorem 6.6","authors_acknowledge":null,"authors_acknowledge_p":null}],"minor_comments":[{"comment":"The abstract states the running time as 1.32736^n, but Theorem 5.10 gives e^{E_t n} with e^{E_t} = 1.3273599467... The rounding to 1.32736 is acceptable, but the paper should be consistent about whether the bound is 1.32736 or 1.3273599467... in the abstract and introduction.","section":"Abstract","authors_acknowledge":null,"authors_acknowledge_p":null},{"comment":"Figure 1 is referenced but not included in the manuscript. The workflow description is clear enough without it, but the figure should be included for completeness.","section":"Section 1.2, Figure 1","authors_acknowledge":null,"authors_acknowledge_p":null},{"comment":"The definition of a block uses the term 'τ-block' but τ is not defined. It appears to be the number of clauses, but this should be clarified.","section":"Section 2.2, Definition 2.4","authors_acknowledge":null,"authors_acknowledge_p":null},{"comment":"In Algorithm 2, line 17: 'l←and arbitrary literal that is set to1inα prev' should be 'l←an arbitrary literal that is set to1inα prev'. Also, line 18: 'C←and arbitrary clause' should be 'C←an arbitrary clause'.","section":"Section 2.5.1, Algorithm 2","authors_acknowledge":null,"authors_acknowledge_p":null},{"comment":"Algorithm 4 (Simple-Expansion) uses the notation 'I_1-chain' but the variable is named 'I_1-chain' in the algorithm and 'I_{1-chain}' in the text. This should be consistent.","section":"Section 3.1, Algorithm 4","authors_acknowledge":null,"authors_acknowledge_p":null},{"comment":"The proof of Lemma 3.4 uses the bound ν_1 ≤ n log c^* / log 3 + O(1). This relies on the assumption that all chains are 1-chains, which is stated in the algorithm description. However, the bound should be justified more explicitly, perhaps by referencing the branching cost formula.","section":"Section 3.2, Lemma 3.4","authors_acknowledge":null,"authors_acknowledge_p":null},{"comment":"The branching cost for a chain S is given as b(S) = 2^{N_p(S)} 3^{1+N_n(S)} (7/3)^{N_t(S)}. The factor 2^{N_p(S)} should be 2^{N_p(S)}? Actually, from Table 2, p has branch number 2, so it should be 2^{N_p(S)}. The text says '2^{N_p(S)}' but the exponent is not clearly formatted. Please ensure the formula is correctly typeset.","section":"Section 5.1.1","authors_acknowledge":null,"authors_acknowledge_p":null},{"comment":"The proof of Lemma 5.8 for chains uses the bounds on m_w from Theorem A.6 and Lemmas A.7, A.8. The numerical values for m_n, m_p, m_t are given as 173/99, 79/45, 25/19. However, these are fractions that should be simplified or given as decimals for clarity. Also, the margin increments Δ_n, Δ_p, Δ_t are computed as positive, but the numerical values (0.00142, 0.00157, 0.00044, 0.00467) seem to have four values for three increments. Please check the arithmetic.","section":"Section 5.2, Lemma 5.8","authors_acknowledge":null,"authors_acknowledge_p":null},{"comment":"The fiber-extension identity (7) is a key lemma. The proof sketch is brief; it would be helpful to include a more detailed derivation, perhaps showing the substitution step explicitly.","section":"Appendix A, Lemma A.5","authors_acknowledge":null,"authors_acknowledge_p":null},{"comment":"The lemma statement is incomplete: 'A(B)≥ ...' is given but the right-hand side is not fully displayed. The proof says 'By Equation 11 and 12, the conclusion follows by collecting terms.' This is insufficient; the derivation should be shown.","section":"Appendix B, Lemma B.1","authors_acknowledge":null,"authors_acknowledge_p":null},{"comment":"Table 3 is referenced but not included. This is a critical omission because the proof of Lemma B.2 relies on it. The authors should either include the table or provide an alternative argument.","section":"Appendix B, Table 3","authors_acknowledge":null,"authors_acknowledge_p":null},{"comment":"The paper contains several typographical errors and awkward phrasings (e.g., 'the algorithm chooses between derandomized local search guided by the block structure and enumeration of block assignments together with selected port variables, reducing the remaining formula to 2-SAT'). A thorough proofreading is recommended.","section":"General","authors_acknowledge":null,"authors_acknowledge_p":null}],"recommendation":"major_revision"},"author_rebuttal":null,"desk_editor":null,"pith_extraction":null,"created_at":"2026-11-13T12:41:56.177926+00:00","model_set":{"reader":"deepseek/deepseek-v4-flash"},"pipeline_version":"pith-pipeline@v1.4.1-daily-deepseek-or-medium","input_kind":null,"input_chars":null,"input_total_chars":null,"passes_missing":null,"published_standing":null,"published_confidence":null,"objection_audit":null,"run_record":null,"basis":{"kind":"not_recorded","source":null,"chars_given":null,"chars_total":null},"receipt":null,"falsifier":null,"supporting_citations":[],"lane_accuracy":{"status":"not yet measured","lane":{"model":"deepseek/deepseek-v4-flash","input_kind":null},"url":"https://pith.science/accuracy"},"review_version":1}