{"id":"97367a96-04f8-404d-aee5-3aa59a8fe027","arxiv_id":"2507.07283","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"Nonogram inference, whether any cell's value is forced in all solutions, is co-NP-complete, and empirically the chance that a filled cell is inferable jumps from near zero to near one as filled-cell density crosses roughly 0.40.","lead":"This paper proves that deciding whether a Nonogram puzzle has at least one cell whose value can be determined without guessing is co-NP-complete, and shows experimentally that this inference problem undergoes a sharp phase transition as the density of filled cells crosses roughly 40 percent. The results square worst-case hardness with the fact that humans enjoy typical puzzles, and give puzzle generators a density knob for tuning difficulty.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Phase-transition metric is forced-filled-only, while INFERENCE includes forced-empty cells; low-density boards with empty rows are almost surely in INFERENCE, so Fig. 5 does not measure the stated transition.","rationale":"The reader's weakest assumption concerns gadget property 4 in the co-NP-hardness proof, and that omission is real: the second case of Theorem 1 only shows the output terminal is not forced, while co-NP-hardness requires no cell anywhere to be forced. I do not dispute that this is a load-bearing gap. However, the single most immediately testable defect in the paper's central narrative is the mismatch between the formal INFERENCE problem and the experimental measure. The reader's rationale notes that the plot only tracks cells forced to be filled, but it does not draw the consequence that all-empty rows make low-density boards positive INFERENCE instances under the formal definition. A 15×15 board at density 0.03 has an empty row with probability about 1 − (1 − 0.63)^15, essentially one, so the claimed low-density regime of 'no inferable cell' cannot be correct for the problem as stated. The paper can be repaired by either restricting the problem statement to forced-filled inference and adjusting the membership certificate, or by extending the experiment to forced-empty cells and redefining the phase transition accordingly. Because this is a major but fixable mismatch, and the reader's conditional verdict already requires metric correction, I keep the conditional verdict unchanged.","tokens_in":6714,"tokens_out":17445,"duration_ms":206607,"concrete_test":"Take one generated 15×15 board at density 0.03 that contains an all-empty row. Extract the row and column descriptions as in Section 3, build the CNF φ, and test satisfiability of φ ∧ x_ij for a cell in that row. If this is unsatisfiable, that cell is forced empty, so the board is in INFERENCE under the definition of Section 2. Then rerun the full protocol counting (a) cells forced empty as well as forced filled and (b) the fraction of boards with at least one forced cell; if the low-density fraction is near one, Fig. 5's phase transition is an artifact of the forced-filled-only metric.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Section 2 defines INFERENCE as the existence of a cell whose value is the same in every solution; this includes cells that are empty in all solutions. The experimental protocol in Section 3, however, only increments a counter when φ ∧ ¬x_ij is unsatisfiable, i.e., only when a cell is forced to be filled; it never tests φ ∧ x_ij to detect cells forced empty. The plotted quantity in Fig. 5 is \"average proportion of filled cells inferred,\" not the probability that an INFERENCE instance has a positive answer. This is not cosmetic. For the Bernoulli generation scheme at ρ = 0.03 and N = 15, each row is empty with probability (1 − ρ)^N ≈ 0.63, so almost every generated board has an all-empty row. Its row description is empty, which forces every cell in that row to be empty in every solution. Such a board is therefore an INFERENCE instance under the paper's formal definition, even though it contributes nothing to inferredFilled. The text's claim that boards below the threshold \"almost surely do not have an inferable cell\" is false for the stated problem; the transition at 0.39–0.42 is a property of forced-filled cells, not of INFERENCE as defined.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies INFERENCE for Nonogram: given a consistent board, decide whether some cell has the same value in every solution. It claims this problem is co-NP-complete (Theorem 1). Membership is argued via polynomial-time checkable certificates that exhibit, for every cell, two solutions differing at that cell. Hardness is attempted by a reduction from Boolean unsatisfiability through circuit gadgets (AND, OR, NOT, wires, crossovers, splitters, input/output terminals), with detailed gadget correctness deferred to the first author's thesis [4]. The paper then reports an empirical phase transition: for random consistent boards generated at filled-cell density rho, the average proportion of filled cells inferred rises sharply around rho in [0.39, 0.42], and SAT-solver propagation effort peaks at the same location. A CNF encoding based on regular expressions is used for the experiments.","tokens_in":6788,"tokens_out":5411,"duration_ms":67714,"significance":"If the hardness proof is completed, the co-NP-completeness classification is a meaningful complement to the known NP-completeness of Nonogram consistency, since inference is a natural formalization of making progress in a puzzle without guessing. The reported threshold phenomenon, if measured against the formal problem, would also be practically relevant for puzzle generation. The paper's certificate for membership in co-NP is simple and correct, and the experimental methodology is transparent enough to be reproduced. However, the current manuscript relies heavily on an unpublished thesis for the gadget lemmas, and the experimental metric does not match the formal definition of INFERENCE, so the central claims are not yet fully established as written.","major_comments":[{"comment":"The only-if direction of the co-NP-hardness proof is incomplete. In the case where C_psi is satisfiable, the proof shows only that the output terminal is not forced, by exhibiting two assignments that give different values at the output. It does not rule out the possibility that some other cell in the board, perhaps inside a gadget, is forced in every solution. The conclusion that the whole board has no inferable cell requires a formal lemma, but the only support given is the unproved gadget property 4, which is asserted without proof and deferred to the first author's thesis [4]. Since the INFERENCE question asks whether any cell is forced, this is load-bearing: a forced cell anywhere in a gadget would invalidate the reduction. Please provide a direct proof, or at least a precise statement of the gadget property and a proof that it implies no cell in the entire construction is forced.","section":"Section 2, proof of Theorem 1"},{"comment":"The experimental metric does not measure the formal INFERENCE problem defined in Section 2. The algorithm tests only whether phi and not x_ij is unsatisfiable, which detects cells forced to be filled; it never tests phi and x_ij, so cells forced to be empty are never counted. Under the formal definition such cells are inferable. At low densities this is not a negligible effect: for N=15 and rho=0.03, a row is empty with probability (1-rho)^N ≈ 0.63, and an empty row description forces every cell in that row to be empty in every solution, making the board an INFERENCE instance. Therefore the claim that boards below the threshold 'almost surely do not have an inferable cell' is false for the stated problem. The transition shown in Figure 5 is a property of forced-filled cells only. The authors should either count forced-empty cells as well (testing phi and x_ij), or explicitly redefine the experiment and all related claims as concerning the proportion of filled cells that are forced to be filled.","section":"Section 3, algorithm Step 5 and Figure 5"}],"minor_comments":[{"comment":"The INFERENCE instance as stated includes 'a mapping of cells to values f', but f is also used for solutions and never appears as an input; the value v in the question is undefined. This should be cleaned up, for example by defining INFERENCE as the existence of a cell c and a bit b such that every solution f satisfies f(c)=b.","section":"Section 2, problem definition"},{"comment":"The prose alternates between 'inferable cell', 'proportion of filled cells inferred', and 'probability of an inferable cell'; these are different quantities. The text should state once, precisely, what is plotted and what the claimed threshold applies to.","section":"Section 3, text near Figure 5"},{"comment":"The certificate description says 'There are 2mn boards to check'; it would be clearer to say that the certificate contains 2mn filled boards (two per cell), and checking each board takes O(mn) time when row and column descriptions are verified. The current wording is not wrong but is easy to misread.","section":"Section 2, proof of co-NP membership"},{"comment":"There is a typo: 'automoton' should be 'automaton'. There is also a redundant phrase 'appears to peak peaks' in the paragraph about propagation counts.","section":"Section 3, CNF encoding paragraph"}],"recommendation":"major_revision","confidential_remarks":"The paper would benefit from being more self-contained: the gadget correctness, the unique-solution lemma, the CNF encoding details, and the formula-size recurrences are all deferred to the first author's thesis [4]. For a journal publication, these should be summarized in an appendix or replaced by clearly stated lemmas with proofs. The mismatch between the formal INFERENCE definition and the experimental metric is the most serious issue and should be resolved before the paper can be accepted. I do not see a fundamental flaw that would require rejection, but the current version does not fully support its two main claims."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things you should know about arXiv:2507.07283. First, the co-NP-completeness of Nonogram INFERENCE is a genuine new result, and the membership argument is clean. Second, the phase-transition section does not actually measure the problem the paper defines. The experiments only count cells forced to be filled; they never test for cells forced to be empty. Since INFERENCE includes both, the plotted curve says nothing about the probability that a random consistent board has an inferable cell. At density 0.03 on a 15x15 board, a row is empty with probability 0.63, and each empty row forces every cell in it empty, so almost every such board is an INFERENCE instance. The paper's claim that boards below the threshold \"almost surely do not have an inferable cell\" is false for the stated problem.\n\nThe hardness proof is plausible but has a gap. Case 2 shows the output terminal is not forced when the formula is satisfiable, but co-NP-hardness requires no cell anywhere to be forced. That step rests on gadget property 4 in Section 2, which is asserted and deferred to the first author's thesis [4]. If that property holds, the proof works; as written it is incomplete. The same thesis supplies the gadget correctness, the CNF encoding details, and the formula-size recurrences. That is a heavy self-citation burden, though not disqualifying.\n\nThe encoding from row descriptions to automata to CNF is described well enough that someone could reimplement it, and the formula-size analysis is honest about the trade-off between runs and clauses. No code ships, the SAT solver is unnamed, the threshold is estimated by eye, and there are no error bars. Those are minor compared to the metric mismatch.\n\nIf the experimental half is meant to study INFERENCE, it needs to test both x_ij and not x_ij, or explicitly redefine the problem as forced-filled inference and adjust the claims. The complexity result is worth a serious referee independent of that.\n\nMy recommendation: send it to peer review, but expect a major revision. The gap in Theorem 1 should be closed by importing the relevant thesis lemma, and the phase-transition section should either measure the defined problem or be relabeled. The paper is for anyone interested in puzzle complexity or average-case behavior, and the core complexity claim is likely correct.","headline":"co-NP-completeness is a genuine new result, but the phase-transition experiments measure only forced-filled cells, not the INFERENCE problem the paper defines.","tokens_in":7485,"tokens_out":3065,"would_cite":false,"duration_ms":30685,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q17","68Q15","68Q25"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper claims that detecting a forced cell in a consistent Nonogram is co-NP-complete and that random boards undergo a phase transition at roughly 0.39–0.42 filled-cell density.","keywords":["Nonogram","inference problem","co-NP-completeness","phase transition","SAT encoding","regular expressions","filled-cell density","consistent board"],"falsifier":"Run the reduction on a satisfiable formula such as $\\psi = (x \\vee y) \\wedge x^*$ and enumerate all solutions of the resulting Nonogram board; if any cell in a gadget other than the output terminal is filled in every solution, gadget property 4 fails and the only-if half of Theorem 1 is unsupported. For the phase transition, measure the inferable-cell fraction on 40x40 boards at densities 0.38, 0.39, 0.40, 0.41, and 0.42: if the curve does not sharpen toward a single threshold as board size grows, the empirical phase transition is not established.","tokens_in":6348,"feed_emoji":"🧩","tokens_out":11934,"duration_ms":125600,"temperature":0.7,"pith_summary":"The paper tries to reconcile the fact that Nonogram is NP-complete to solve yet humans enjoy it by studying inference: whether some cell is forced in every solution of a consistent board. It claims this inference problem is co-NP-complete, meaning it is as hard as proving a Boolean formula unsatisfiable. It also reports an empirical phase transition: for random consistent boards, the proportion of filled cells that are inferable jumps from near zero to near one as filled-cell density crosses roughly 0.39 to 0.42, with SAT solving effort peaking at the transition. If correct, worst-case hardness and practical playability are compatible because typical boards sit far from the difficult threshold.","feed_headline":"Nonogram's safe-move problem is co-NP-complete","feed_subtitle":"Random consistent puzzles flip from no forced cells to nearly all forced around 40% filled density.","key_machinery":"The machinery has two linked pieces. The first is a library of eleven-by-eleven Nonogram gadgets for NOT, AND, OR, wire, splitter, crossover, and terminals, which simulate Boolean circuits; the reduction depends on the property that no gadget's cells can be derived from its own descriptions alone. The second is a line encoding: a description $(l_1,\\ldots,l_t)$ becomes the regular expression $0^*1^{l_1}0^+1^{l_2}0^+\\cdots 1^{l_t}0^*$, which is converted through a DFA into a CNF formula, with the whole board encoded as the conjunction of row and column formulas. The inference test for cell $(i,j)$ checks satisfiability of the board formula together with the assumption that the cell is empty (or filled).","core_discovery":"The central claim is that INFERENCE for Nonogram is co-NP-complete. A negative instance is certified by giving, for every cell, two consistent fillings of the board with opposite values in that cell. Co-NP-hardness is shown by reducing Boolean unsatisfiability: a fresh variable is added to the input formula, a Boolean circuit is built, and the circuit is translated into Nonogram gadgets so that the board has an inferable cell exactly when the circuit is unsatisfiable. Empirically, the paper finds that the average fraction of filled cells whose value is logically forced rises from almost zero to almost one when filled-cell density passes roughly 0.39 to 0.42, and that average solver propagation counts peak in the same region.","pith_inferences":["The authors do not say this, but the location of the threshold suggests a counting argument: below roughly 0.4 density the number of solutions may grow so quickly that no cell is pinned, while above it enough row and column constraints overlap to pin cells; deriving the critical density analytically from run-length statistics would turn the empirical curve into a theorem.","A testable extension is to generate boards from other random models, such as random run-length descriptions or random images, and check whether the same 0.39–0.42 threshold appears; if the threshold moves, the transition is a property of the generation model rather than of Nonogram constraints alone.","The inferability test itself could serve as a puzzle-difficulty metric, letting a designer certify that a generated board has at least one logical step and deliberately place puzzles near the transition when a harder challenge is intended."],"forward_implications":["Solving INFERENCE on all consistent boards is at least as hard as proving unsatisfiability, so unless P = NP no polynomial-time algorithm can always find a safe move.","The empirical curve gives puzzle designers a tuning knob: boards below roughly 0.39 filled-cell density will rarely offer a forced step, while boards above roughly 0.42 will often have nearly every filled cell forced.","The peak in solver effort at the transition, rather than at the largest formulas, indicates that practical difficulty is a property of the inference decision and not just of formula size.","The regular-expression-to-CNF encoding is polynomial in board size, with $O(n^2)$ variables and clauses per line, which is what makes the inference experiments feasible at the board sizes tested."],"supporting_citations":[{"why":"Supplies the 11x11 gadget solutions and the regular-expression-to-CNF encoding; both the co-NP-hardness proof and the experiments defer to it for construction details.","marker":"[4]"},{"why":"Establishes NP-completeness of Nonogram consistency via parsimonious reductions, the baseline that the inference result extends and contrasts with.","marker":"[16]"},{"why":"Shows the inference problem is co-NP-complete for Minesweeper, the model this paper transfers to Nonogram.","marker":"[13]"},{"why":"Identifies clause-to-variable ratio as the phase-transition parameter for SAT, the template for using filled-cell density as the Nonogram parameter.","marker":"[9]"},{"why":"Reports a phase transition in Minesweeper consistency, a prior puzzle transition against which the Nonogram transition is situated.","marker":"[3]"},{"why":"Reports Sudoku's freezing transition, a second puzzle transition used for comparison.","marker":"[11]"},{"why":"Warns about the definition of random instances and motivates the consistent-board generation model used in the experiments.","marker":"[5]"}],"fun_headline_variants":["Nonogram inference is co-NP-complete, phase transition found","Nonogram's forced-cell problem is co-NP-hard, sharp transition","Inference in Nonogram: co-NP-complete, density flips at 0.4","Nonogram safe moves: co-NP-complete, with phase shift near 40%","Deciding Nonogram inference: co-NP-complete, phase transition at ~0.4"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The only-if direction of the co-NP-hardness proof depends on the unproved assertion that no gadget's cells are forced by that gadget's own constraints alone, which the paper defers to the first author's thesis; if any gadget cell were internally forced, a satisfiable formula could still produce an inferable cell.","fun_headline_variants_meta":{"raw":{"variants":["Nonogram inference is co-NP-complete, phase transition found","Nonogram's forced-cell problem is co-NP-hard, sharp transition","Inference in Nonogram: co-NP-complete, density flips at 0.4","Nonogram safe moves: co-NP-complete, with phase shift near 40%","Deciding Nonogram inference: co-NP-complete, phase transition at ~0.4"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000163,"raw_usage":{"total_tokens":1203,"prompt_tokens":863,"completion_tokens":340,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":479,"completion_tokens_details":{"reasoning_tokens":230}},"tokens_in":479,"tokens_out":340,"duration_ms":3881,"temperature":1.0,"reasoning_tokens":230,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T18:46:05.921700+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the reduction on a satisfiable formula such as $\\psi = (x \\vee y) \\wedge x^*$ and enumerate all solutions of the resulting Nonogram board; if any cell in a gadget other than the output terminal is filled in every solution, gadget property 4 fails and the only-if half of Theorem 1 is unsupported. For the phase transition, measure the inferable-cell fraction on 40x40 boards at densities 0.38, 0.39, 0.40, 0.41, and 0.42: if the curve does not sharpen toward a single threshold as board size grows, the empirical phase transition is not established.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the 11x11 gadget solutions and the regular-expression-to-CNF encoding; both the co-NP-hardness proof and the experiments defer to it for construction details."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Establishes NP-completeness of Nonogram consistency via parsimonious reductions, the baseline that the inference result extends and contrasts with."},{"cited_title":"The Mathematical Intelligencer33, 5–17 (2011)","cited_arxiv_id":null,"evidence_quote":"Shows the inference problem is co-NP-complete for Minesweeper, the model this paper transfers to Nonogram."},{"cited_title":"Proceedings Tenth National Conference on Artificial Intelligence (07 1992)","cited_arxiv_id":null,"evidence_quote":"Identifies clause-to-variable ratio as the phase-transition parameter for SAT, the template for using filled-cell density as the Nonogram parameter."},{"cited_title":"In: FUN with Algo- rithms 2020 (2020)","cited_arxiv_id":null,"evidence_quote":"Reports a phase transition in Minesweeper consistency, a prior puzzle transition against which the Nonogram transition is situated."},{"cited_title":"In: 2018 IEEE 30th International Conference on Tools with Artificial Intelligence (ICTAI)","cited_arxiv_id":null,"evidence_quote":"Reports Sudoku's freezing transition, a second puzzle transition used for comparison."},{"cited_title":"Discrete Applied Mathematics5(1), 77–87 (1983)","cited_arxiv_id":null,"evidence_quote":"Warns about the definition of random instances and motivates the consistent-board generation model used in the experiments."}],"review_version":1}