{"id":"712d550c-59ca-4e30-ab2c-323d751ad219","arxiv_id":"2511.18639","paper_version":2,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A URSA/SAT workflow specifies NP problems as certificate checkers and verifies NP-reductions for all instances up to a chosen size, covering full correctness in some cases and soundness in others.","lead":"This paper presents a SAT-based methodology, built on the URSA constraint solver, for writing and checking reductions between NP-complete problems. It demonstrates bounded, machine-checked verification of reductions over all instances of a fixed size, for example clique-to-vertex-cover, 3SAT-to-3-colouring, and SAT-to-3SAT.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"UNSAT only verifies the reduction modulo the unverified certificate relation; an inconsistent bCertificateReduction makes the assertion vacuously UNSAT, so the paper's 'confirms correctness' claim lacks a required non-vacuity check.","rationale":"The reader's verdict identifies URSA encoding fidelity as the weakest assumption. I agree that is a real risk, but I found a more internal, load-bearing gap: the UNSAT result is only as strong as the user-defined bCertificateReduction. In Section 5.1 the paper states that UNSAT 'confirms correctness for k=20, for any graph with 50 vertices.' That conclusion relies not only on the encoding being faithful, but on the certificate relation being a genuine bijection (or, for the soundness checks in 5.2/5.3, being total on target certificates). The paper never states or verifies this precondition. A contradictory bCertificateReduction (e.g., set to false) makes every assertion trivially UNSAT, so the method would 'verify' even a broken reduction. The concrete examples are not vacuous—in 5.1 the relation is complementary, in 5.2/5.3 it functionally determines source variables from target colours—but the framework as described offers no guard, and Section 7's general claim ('simple, operational verification of reduction correctness or soundness') overstates what the raw UNSAT output establishes. The proposed negative-control test settles the concern by showing the assertion's result can be manufactured by the certificate conjunct alone. Because the examples themselves likely pass a non-vacuity check, I would not reject the paper; but I would make acceptance conditional on the authors adding an explicit condition/check that bCertificateReduction is satisfiable and total/bijective on the relevant certificate spaces, and on stating this caveat in Sections 5 and 7.","tokens_in":20528,"tokens_out":19423,"duration_ms":209816,"concrete_test":"As a negative control, take the Example 5.1 code (nV=6, nK=4) and change the line `bCertificateReduction = true;` to `bCertificateReduction = false;`, keeping all verifier and reduction code unchanged. Re-run URSA on the original assertion `assert((bClique ^^ bVertexCover) && bCertificateReduction)`. If it still returns UNSAT, the assertion's unsatisfiability can be produced entirely by the certificate-relation conjunct; hence, without an additional check that bCertificateReduction is satisfiable and total/bijective on the certificate space, an UNSAT result cannot by itself be read as confirmation of the reduction. This check directly tests whether the paper's Section 5 inference is self-contained.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The load-bearing step in Section 5 equates 'the assertion has no solutions' with 'the reduction is correct/sound.' But every verification assertion contains the conjunct bCertificateReduction. If this conjunct is unsatisfiable, or (for soundness-only checks) is not satisfiable for every target certificate, then the whole assertion is UNSAT regardless of the reduction's correctness. The paper gives no check that bCertificateReduction is satisfiable, total on target certificates (for soundness), or a bijection between certificate spaces (for full correctness). In the supplied examples the relations are total (Example 5.1 imposes bBelongsVertexCover[i] = !bBelongsClique[i]; Example 5.2 defines bV[i] from the colour of the corresponding variable node), so the published UNSAT results are meaningful. But the general methodology described in Sections 5 and 7 does not state or enforce this precondition. Consequently, the central claim that an UNSAT assertion 'confirms correctness/soundness' is not self-contained: it is true only under an unverified, human-supplied condition on the certificate relation. This is an internal gap, not merely external toolchain trust.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a methodology for specifying, testing, and boundedly verifying reductions between NP-complete problems using the URSA SAT-based constraint solver. After fixing an input size, the source and target problems are represented by their certificate verification procedures, the reduction by an imperative symbolic transformation, and the user adds a certificate-relation conjunct bCertificateReduction. The resulting combined formula—either a XOR of the two certificate checks (for correctness) or a source-unsatisfiable/target-satisfiable formula (for soundness)—is translated to SAT. Unsatisfiability is interpreted as: the reduction is correct/sound for all instances of the fixed size. The method is illustrated on three reductions: k-Clique to l-Vertex Cover (full correctness), 3SAT to 3-Coloring (soundness), and SAT to 3SAT (soundness). The paper also compares the approach with REDNP, Karp, and cookbook reductions. The main caveats noted in the paper are that the verification is size-bounded and does not replace a general proof.","tokens_in":20825,"tokens_out":14769,"duration_ms":148180,"significance":"If the methodology works as claimed, it gives a practical workflow for obtaining bounded, solver-checked evidence for reductions, useful in research and teaching. The paper is honest about the boundedness of the verification and about the fact that the ultimate proof would require a proof assistant. Strong points are the fully worked URSA code for three nontrivial reductions, the concrete UNSAT experiments with reported formula sizes and runtimes, and the clear related-work comparison. The central methodological inference, however, is incomplete as written: it requires an explicit totality/non-vacuity condition on bCertificateReduction and a formal correctness statement for the encoding. These are local, fixable issues rather than flaws in the examples.","major_comments":[{"comment":"The inference from UNSAT to correctness is valid only under an unstated precondition on bCertificateReduction. If this conjunct is unsatisfiable, the whole assertion is UNSAT regardless of the reduction, so the reported 'confirms correctness/soundness' is vacuous. Formally, from UNSAT of (bY ^^ bX) && R one can derive the source-to-target implication only if R is left-total (every source certificate has at least one related target certificate), and the target-to-source implication only if R is right-total (every target certificate has at least one related source certificate). The examples here happen to satisfy these conditions—in Example 5.1 bBelongsVertexCover = ¬bBelongsClique is a bijection, and in Examples 5.2 and 5.3 bCertificateReduction projects the target certificate onto the source assignment. But Sections 5 and 7 present the method without stating or checking these properties.","section":"§5, general verification scheme; Examples 5.1–5.3"},{"comment":"The central claim that an UNSAT assertion verifies a reduction for all instances of a fixed size is argued only informally. Provide a correctness lemma stating the precise relationship between the URSA certificate-check formulas bY/bX and Cert_Y/Cert_X, and the conditions under which UNSAT of the asserted formula implies the reduction is correct (or sound). The lemma must also make explicit the trust assumptions on URSA's symbolic execution and fixed-width encoding; the phrase 'bClique and bVertexCover collectively encompass all possible input graphs of the given size' presupposes that the encoding has no spurious bit patterns and respects the required natural-number bounds. Without such a statement, the outputs are tool-dependent evidence rather than a verification result.","section":"§5, esp. Figure 5 and §2.3"},{"comment":"The criterion offered for when full correctness is verifiable vs. soundness-only—'all variables defining the first certificate occur in the second, and vice versa'—is not a correct or sufficient condition. Variable occurrence is neither necessary nor sufficient for the required totality of bCertificateReduction. A relation can be total between certificates even when variable sets differ; conversely, overlapping variable sets do not guarantee a total relation. Whether full correctness can be verified depends on the ability to define a left- and right-total certificate relation in the URSA encoding, not on syntactic variable containment. This paragraph should be rewritten accordingly.","section":"§5, last paragraph (p. 21)"}],"minor_comments":[{"comment":"Please include the URSA source files and exact solver versions/settings for the reported UNSAT results, so that the experiments are reproducible.","section":"§5 and general"},{"comment":"Typos: 'cluque' in the Figure 3/4 captions and surrounding text; 'anwser' in §4; 'a clique of size at most k' at the end of Example 2.1 should be 'at least k'.","section":"Figures 3–4, §4, Example 2.1"},{"comment":"The sentence 'since the set of variables in b3colouring is a strict superset ... if b3colouring is true in some valuation, b3SAT will be true too' is confusing and, read literally, asserts the reduction property that the paper is trying to verify. Please rephrase.","section":"§5.2"},{"comment":"Calling the verification 'fundamentally, an enumeration-based argument' is misleading: the SAT encoding is symbolic and does not enumerate input instances. Consider 'symbolic bounded verification' or similar terminology.","section":"§7"}],"recommendation":"major_revision","confidential_remarks":"The reader's accept verdict is understandable because the worked examples are correct and the paper's claims are carefully hedged. However, the general method needs a precise statement of the certificate-relation conditions before the paper can be accepted. These conditions are easy to state and check, so the required changes are a revision rather than a rejection. The author's reliance on URSA is not circular, but providing the URSA scripts or generated CNF would materially strengthen the verification claims."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nYou should know this paper delivers a modest but genuine methodological contribution. The trick is to leave the input instance (graph, formula) symbolic in URSA, run the certificate checkers for both problems plus a relation linking the two certificates, and then ask a SAT solver whether the two outcomes can differ. An UNSAT answer is machine-checked evidence that the reduction is correct (or at least sound) for every instance of that fixed size. That is stronger than REDNP's fixed test cases and Karp's generated instances, and it is not present in cookbook reductions. The three worked examples are concrete, the code is readable, and the paper explicitly distinguishes equisatisfiability from equivalence, which is the right thing to emphasize. It also honestly labels Examples 5.2 and 5.3 as soundness-only. The limitations of bounded size are stated plainly. Credit where due: this is a useful tool for the reduction-writing community and for teaching.\n\nThe soft spots are real but not fatal. The biggest one, which the stress-test note pins down correctly: an UNSAT result is only meaningful relative to the certificate relation bCertificateReduction. If that relation is unsatisfiable, or if it does not cover every source certificate (for completeness) or every target certificate (for soundness), the assertion can be UNSAT for the wrong reason. The examples happen to use total relations — complement for Clique/VertexCover, variable-node color equivalence for 3SAT-to-3COL, variable equivalence for SAT-to-3SAT — so the published UNSAT results are meaningful. But the general methodology in Sections 5 and 7 never states this precondition or tells the user to check it. That is an internal gap in the central claim as written, not just an external trust issue.\n\nSecond, there is no formal semantics for the URSA encoding or a proof that the translation to SAT is sound and complete, and no shipped code or independent solver certificates. That limits reproducibility in the way the reader's report says. Third, the complexity arguments are informal; fine for a methods paper, but they should be marked as such. The self-citation to [Jan10] is reasonable here; the verification results are independent of URSA's earlier theorems.\n\nWho should read it: anyone developing NP reductions or teaching them, and people building verification tools. It is not a breakthrough, but it is a working method with honest boundaries.\n\nMy recommendation: send it to peer review. Ask the authors to add an explicit totality/non-vacuity condition on the certificate relation, and ideally to ship the URSA scripts so the results can be rerun. With those additions it would be a solid, citable paper.","headline":"Bounded all-instances reduction checking via symbolic SAT is a real and useful idea, but the paper's 'UNSAT means correct' claim needs an explicit non-vacuity condition on the certificate relation.","tokens_in":21281,"tokens_out":4926,"would_cite":true,"duration_ms":50999,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q17","68Q25"],"pacs":[],"model":"deepseek-v4-flash","headline":"A SAT-based workflow lets a user verify NP-complete reductions for fixed instance sizes.","keywords":["SAT","NP-completeness","reductions","verification","symbolic execution","equisatisfiability","bounded verification","constraint solving"],"falsifier":"Encode a deliberately wrong reduction — for instance, clique-to-vertex-cover with the size equation changed from l = n - k to l = k — and run the verification at a small fixed size such as n = 6. If the solver reports unsatisfiable for this broken reduction, the method cannot distinguish correct from incorrect reductions and the central claim fails; if it returns a model, the method is catching the error as claimed.","tokens_in":20428,"feed_emoji":"🧩","tokens_out":6102,"duration_ms":56431,"temperature":0.7,"pith_summary":"The paper claims that a SAT-based constraint solver can become a practical workbench for NP-completeness reductions. You write, in the solver's imperative-declarative language, the source problem's certificate checker, the reduction, the target problem's certificate checker, and a clause linking the two certificates; the solver turns the whole thing into one propositional formula. If the formula is unsatisfiable, the reduction is correct for all inputs of that fixed size; when only one direction is encodable, the same setup verifies soundness. The paper demonstrates this on reductions among SAT, 3SAT, 3-colouring, k-clique, and l-vertex cover, including a full verification of the clique-to-vertex-cover reduction for every graph on 50 vertices with k=20. This matters because reduction proofs are error-prone and existing tooling mostly tests individual instances rather than certifying entire size classes.","feed_headline":"UNSAT query certifies NP-reductions for fixed input sizes","feed_subtitle":"Encoding source, target, and certificate link as one SAT formula, an unsatisfiable answer proves the reduction for that size.","key_machinery":"Symbolic execution inside the URSA constraint solver is the engine: unspecified inputs become fixed-width vectors of Boolean variables, the certificate checkers and the reduction are run symbolically, and the user's assert becomes a propositional formula sent to a SAT solver. The load-bearing identity is the certificate-correspondence assertion, a formula of the form 'the two answers differ AND the two certificates are linked by the intended translation'. Unsatisfiability of this combined formula certifies correctness for the chosen instance size. The paper's key conceptual move is explaining why equisatisfiability alone is insufficient and why the certificate link closes the gap.","core_discovery":"On its own terms, the central claim is that one unsatisfiability query can certify a reduction between NP-complete problems for all instances of a fixed size, provided the encoding is faithful. The subtlety the paper identifies is that the two certificate-checking formulas are equisatisfiable, not logically equivalent, so asserting only that the answers differ proves nothing; the user must also assert a certificate-correspondence condition, such as 'the clique and the vertex cover are complements'. With that link, an UNSAT answer is a machine-checked, bounded proof of correctness for that input size. Without it, the method still yields soundness checks whenever all variables of the source ce","pith_inferences":["The bounded verification could be combined with an inductive argument or a generic proof to yield full, unbounded correctness, a step the paper does not take.","The same fixed-size verification pattern generalizes beyond classical NP-completeness, e.g., to many-one reductions between promise problems or parameterized problems, whenever a certificate relation is expressible.","A practical benchmark would apply the method to intentionally broken reductions and measure whether the SAT solver reliably returns counterexamples at small sizes; the paper's narrative suggests this works but does not systematically measure it."],"forward_implications":["A designed reduction can be machine-checked for correctness or soundness for every input of a given size, not just on hand-picked test cases.","The same specification doubles as a solver: once the source problem is solved, the reduction plus target certificate checker solves the target problem.","The method offers an interactive debugging loop: a satisfying model is a concrete counterexample that pinpoints the bug in the reduction code.","For reductions whose certificate variables correspond in both directions, full correctness is certifiable; for others, soundness remains verifiable whenever the source certificate's variables appear in the target's.","The ground-bounded loop structure of URSA makes the polynomial-time requirement of the reduction and certificate checks immediately visible."],"fun_headline_variants":["UNSAT certifies NP-reductions, but only with certificate link","SAT solver proves reductions when certificates are tied","Bounded proof for NP-reductions via one UNSAT query","Machine-checked reductions: UNSAT needs certificate link"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The method's UNSAT answer is only as trustworthy as the fixed-width symbolic encoding: if the URSA specification does not range over exactly the intended legal instances, or if the translation to SAT adds or drops solutions, the verification says nothing about the actual reduction.","fun_headline_variants_meta":{"raw":{"variants":["UNSAT certifies NP-reductions, but only with certificate link","SAT solver proves reductions when certificates are tied","Bounded proof for NP-reductions via one UNSAT query","Machine-checked reductions: UNSAT needs certificate link"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000673,"raw_usage":{"total_tokens":2827,"prompt_tokens":594,"completion_tokens":2233,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":338,"completion_tokens_details":{"reasoning_tokens":2175}},"tokens_in":338,"tokens_out":2233,"duration_ms":16101,"temperature":1.0,"reasoning_tokens":2175,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-03T20:41:04.048811+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Encode a deliberately wrong reduction — for instance, clique-to-vertex-cover with the size equation changed from l = n - k to l = k — and run the verification at a small fixed size such as n = 6. If the solver reports unsatisfiable for this broken reduction, the method cannot distinguish correct from incorrect reductions and the central claim fails; if it returns a model, the method is catching the error as claimed.","supporting_citations":[],"review_version":1}