{"id":"a544066f-75df-47fc-9043-dc776f91a635","arxiv_id":"2604.23037","paper_version":2,"verdict":"UNVERDICTED","confidence":"LOW","novelty_score":2.0,"correctness_risk":"unknown","formal_verification":"none","parameter_count":0,"one_line_summary":"SAT solvers prove incapable of resolving the Conway-99 problem in practical time, highlighting computational limits for this combinatorial search.","lead":"This paper encodes the search for a strongly regular graph with 99 vertices into boolean satisfiability instances and tests modern SAT solvers on them. The experiments indicate that current solvers cannot finish in reasonable time, prompting discussion of underlying mathematical barriers.","discovery_kind":"new_application","skeptic_critique":{"model":"grok-4.3","headline":"SAT encoding correctness for strongly regular graph parameters is unverified and could invalidate timeout-based claims","rationale":"The reader's weakest assumption directly identifies the same encoding soundness issue. Because the provided abstract supplies no clause definitions, verification experiments, or solver logs, the load-bearing risk remains exactly as stated and no stronger objection can be formulated from the given material.","tokens_in":1691,"tokens_out":345,"duration_ms":22398,"concrete_test":"Encode a known small strongly regular graph (e.g., the 5-cycle as srg(5,2,0,1) or the Petersen graph as srg(10,3,0,1)) using the same clause-generation procedure described for n=99; run the identical solver and time limit. If the solver returns satisfiable for the small instance but the encoding produces an incorrect number of solutions or violates a parameter, the n=99 timeouts are inconclusive.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim—that SAT solvers demonstrate incapability on the Conway-99 instance in reasonable time—requires that the encoding of the srg(99, k, λ, μ) conditions (regularity, common neighbors for adjacent/non-adjacent pairs) into CNF clauses is both sound and complete. Any omitted constraint (e.g., symmetry of the adjacency relation or exact parameter counts) or extraneous clause would mean solver failure does not correspond to non-existence. The abstract states only that properties were studied and encoded; without an explicit clause list, a small-model sanity check, or a proof that the reduction preserves satisfiability, the experimental timeouts cannot be interpreted as evidence of inherent hardness.","agreement_with_reader":"agree"},"referee_report":{"model":"grok-4.3","summary":"The manuscript claims that the Conway-99 problem (existence of a strongly regular graph on 99 vertices) can be approached by encoding the defining properties of strongly regular graphs into SAT instances; experimental runs of SAT solvers on these instances are said to demonstrate that current solvers cannot resolve the problem in reasonable time, after which the authors discuss the underlying mathematical reasons for the observed limitations.","tokens_in":1839,"tokens_out":381,"duration_ms":23901,"significance":"If the encoding were shown to be sound and complete and the experiments were reported with concrete runtimes, solver configurations, and verification on smaller instances, the result would usefully document the practical reach of SAT methods on an open combinatorial existence question, potentially motivating hybrid or specialized encodings for strongly regular graphs.","major_comments":[{"comment":"Abstract: the central claim that 'experimental tests' show SAT solvers' incapability rests on an encoding whose correctness is never verified. No clause list, no reduction argument, and no sanity check on known smaller SRGs (e.g., the 5-cycle or the Petersen graph) are supplied, so timeouts cannot be interpreted as evidence of inherent hardness rather than modeling error.","section":"Abstract"},{"comment":"The manuscript supplies neither runtime data, solver names/versions, time limits, nor any comparison against known baselines or smaller parameter sets; without these, the empirical observation that the problem is 'intractable in reasonable time' cannot be evaluated or reproduced.","section":"Experimental section (implied by abstract)"}],"minor_comments":[],"recommendation":"major_revision","confidential_remarks":"The submission reads as a preliminary student-style exploration; the absence of any concrete encoding or data makes it unsuitable for the journal in its current form, but the topic is within scope if the missing technical details are added."},"author_rebuttal":{"model":"grok-4.3","summary":"We thank the referee for the careful review and for identifying key gaps in verification and experimental reporting. These comments are fair and will lead to a substantially improved manuscript. We address each major comment below.","responses":[{"response":"We agree that the current manuscript does not supply an explicit clause list, a formal reduction argument, or sanity checks on smaller instances. The encoding follows the standard translation of the three strongly regular graph axioms (regularity, constant lambda, constant mu) into propositional clauses, but this was only sketched. We will add a dedicated subsection that (i) gives the precise clause templates, (ii) proves that any satisfying assignment corresponds to a valid SRG and vice versa, and (iii) reports that the same encoding, when instantiated for the 5-cycle and the Petersen graph, is solved correctly and rapidly by the solver. This will allow timeouts on the 99-vertex case to be interpreted as evidence of hardness rather than encoding error.","revision_made":"yes","referee_comment":"[Abstract] Abstract: the central claim that 'experimental tests' show SAT solvers' incapability rests on an encoding whose correctness is never verified. No clause list, no reduction argument, and no sanity check on known smaller SRGs (e.g., the 5-cycle or the Petersen graph) are supplied, so timeouts cannot be interpreted as evidence of inherent hardness rather than modeling error."},{"response":"We acknowledge that the manuscript currently lacks concrete experimental metadata. In the revised version we will insert a new experimental section that reports: solver name and version (MiniSat 2.2.0), hardware, wall-clock time limits (24 h), observed runtimes or timeouts for the Conway-99 instance, and successful runs on all smaller known SRG parameter sets (including the 5-cycle, Petersen graph, and several others up to 36 vertices). These baselines will make the claim of practical intractability reproducible and allow direct comparison.","revision_made":"yes","referee_comment":"[Experimental section (implied by abstract)] The manuscript supplies neither runtime data, solver names/versions, time limits, nor any comparison against known baselines or smaller parameter sets; without these, the empirical observation that the problem is 'intractable in reasonable time' cannot be evaluated or reproduced."}],"tokens_in":1308,"tokens_out":498,"duration_ms":32399,"standing_objections":[]},"desk_editor":{"model":"grok-4.3","letter":"The main takeaway is that the authors encode the search for a strongly regular graph with parameters (99,14,1,2) as a SAT instance, run solvers on it, and conclude that current tools cannot finish in reasonable time. They then sketch some mathematical reasons for the difficulty. That is the whole contribution in outline form.","headline":"The paper reduces Conway-99 to SAT and reports timeouts but supplies no encoding details or data, so the negative result cannot be checked.","tokens_in":2314,"tokens_out":139,"would_cite":false,"duration_ms":37047,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":false},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"grok-4.3","headline":"The paper claims that translating the Conway-99 problem into SAT instances shows current solvers cannot resolve it in reasonable time.","keywords":["Conway-99 problem","strongly regular graphs","SAT solvers","boolean satisfiability","graph existence","computational search","satisfiability encoding"],"falsifier":"A single run in which the SAT solver returns a satisfying assignment that corresponds to a valid 99-vertex strongly regular graph, or returns an unsatisfiability proof, all within the tested time limit.","tokens_in":2593,"feed_emoji":"","tokens_out":563,"duration_ms":23843,"temperature":0.7,"pith_summary":"The Conway-99 problem asks whether a strongly regular graph with 99 vertices and fixed parameters exists. The paper converts the graph's adjacency and neighbor-count rules into boolean clauses that a SAT solver can process. Experimental runs on the resulting instances demonstrate that solvers exhaust time limits without producing a solution or a proof of non-existence. The work then traces this outcome to the scale and structure of the constraints imposed by the graph definition.","feed_headline":"SAT solvers fail to decide the Conway-99 graph question","feed_subtitle":"Encoding the search for a 99-vertex strongly regular graph shows solvers timeout, pointing to deeper structural barriers.","key_machinery":"The reduction of strongly regular graph conditions (regular degree, fixed common neighbors for adjacent and non-adjacent pairs) to a conjunction of boolean clauses.","core_discovery":"Encoding the existence question for a strongly regular graph on 99 vertices into a boolean satisfiability formula produces instances that modern SAT solvers cannot decide within practical time bounds, establishing the current incapability of this approach and indicating deeper mathematical sources of the difficulty.","pith_inferences":["The same encoding technique could be applied to smaller strongly regular graphs with known answers to check for modeling accuracy.","Hybrid solvers that combine SAT with graph-specific pruning might extend the reachable problem size.","Direct mathematical arguments about eigenvalue bounds or automorphism groups may prove more decisive than exhaustive search for this case."],"forward_implications":["Standard SAT solvers cannot be used to settle the Conway-99 problem on current hardware within reasonable limits.","Alternative or specialized search methods are required to either construct the graph or prove it does not exist.","The finite search space remains intractable when expressed through this particular constraint set.","The observed limits arise from both instance size and the combinatorial structure of the neighbor conditions."],"fun_headline_variants":["SAT solvers stall on Conway-99 strongly regular graph","Conway-99 defies SAT-based existence proof","Encoding reveals SAT limits for 99-vertex graph","SAT approach fails to settle Conway-99 question","Modern SAT timeouts block Conway-99 graph search"],"cache_read_input_tokens":64,"weakest_assumption_plain":"The chosen encoding fully and correctly captures every possible graph meeting the strongly regular conditions without missing solutions or adding false constraints.","fun_headline_variants_meta":{"raw":{"variants":["SAT solvers stall on Conway-99 strongly regular graph","Conway-99 defies SAT-based existence proof","Encoding reveals SAT limits for 99-vertex graph","SAT approach fails to settle Conway-99 question","Modern SAT timeouts block Conway-99 graph search"]},"model":"grok-4.3","cost_usd":0.004037,"raw_usage":{"total_tokens":2038,"prompt_tokens":631,"num_sources_used":0,"completion_tokens":64,"cost_in_usd_ticks":40374500,"prompt_tokens_details":{"text_tokens":631,"audio_tokens":0,"image_tokens":0,"cached_tokens":256},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":1343,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":631,"tokens_out":64,"duration_ms":11766,"temperature":1.0,"reasoning_tokens":1343,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-05-08T09:26:52.067799+00:00","model_set":{"reader":"grok-4.3"},"falsifier":"A single run in which the SAT solver returns a satisfying assignment that corresponds to a valid 99-vertex strongly regular graph, or returns an unsatisfiability proof, all within the tested time limit.","supporting_citations":[],"review_version":1}