{"id":"bfa23405-5557-434b-a34d-fdf7fc498c3a","arxiv_id":"2506.09133","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Deciding whether a COPE matrix has a noncontextual ontological model of dimension k is shown to lie between (nm)^Ω(r) and poly(b,m,n)^O(k^2), and a 5x5 example separates the minimal noncontextual ontic size (5) from the minimal unconstrained ontic size (4).","lead":"Yianni and Shahandeh give complexity bounds for deciding when a generalized probabilistic theory admits a noncontextual hidden-variable model of a given size, by recasting the problem as a nonnegative matrix factorization and an intermediate-simplex question in geometry. They also exhibit a concrete matrix where the smallest noncontextual model is larger than the smallest ordinary hidden-variable model.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Central reduction depends on an unverified, same-author rank-separation criterion; if the ENMF–noncontextuality equivalence fails, the complexity results describe a matrix problem, not contextuality.","rationale":"The reader's weakest-assumption analysis and my own reading converge: the rank-separation criterion imported from Ref [9] is the hinge connecting the paper's matrix-factorization results to generalized contextuality. The paper offers no independent proof of this equivalence, and Section IV's comparison to simplex embeddability is suggestive rather than a derivation. This is a genuine load-bearing concern because a counterexample would leave the complexity theorems intact as statements about ENMF, but would disconnect them from the paper's claimed subject matter. I do not see an internal contradiction that would make the main construction false as stated; the explicit 5-vs-4 example is backed by closed-form factorizations and an exact dual LP certificate, which is real supporting evidence. I also note a dimension inconsistency in Theorem 10: the stated dimensions (m+k−r) x (n+2k−2r) appear swapped relative to the product A_b B_b constructed in the proof, which has dimensions (m+2k−2r) x (n+k−r); this looks like a typo rather than a fatal flaw, but it reinforces the need for independent verification. Corollary 7's 'choose G=A' step is also not self-evident, since a rank-r coefficient matrix mapping all vertices of A to B is a stronger condition than one mapping a nested G; this is a second soft spot, but the external rank-separation criterion is more foundational. A targeted computational or analytic check should settle the equivalence, and the verdict remains CONDITIONAL pending that check.","tokens_in":27150,"tokens_out":19980,"duration_ms":220812,"concrete_test":"Independently verify the rank-separation criterion on small scenarios: enumerate all 3x3 and 4x4 COPE matrices with entries in {0, 1/2, 1} and, for each, compare (a) existence of an ENMF with inner dimension k, checked by enumerating rank-r nonnegative factorizations, against (b) existence of a noncontextual ontological model, decided by the linear program of Selby et al. (Ref [18]) or by the simplex-embeddability conditions of Schmid et al. (Ref [35]). A single disagreement falsifies the converse direction of Corollary 2 as used in this paper; agreement on the full enumeration would supply the missing independent support.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Section II.C imports from Ref [9] (Lemma 1, Corollary 2) the claim that a COPE C admits a noncontextual ontological model iff it admits an ENMF C=RE with rank C=rank R=rank E. Every central result—Corollary 3's ETH lower bound, Corollary 13's upper bound, and the 5-vs-4 ontic-size separation—is a statement about ENMF existence, not about the operational definition of noncontextuality. The criterion is neither rederived nor independently verified here; Section IV's identification with simplex embeddability (Refs [24,35]) is a sketch, not a proof. The necessary direction (noncontextual model implies ENMF) is plausible, but the converse (ENMF implies a noncontextual model) is the load-bearing direction and is exactly where a rank condition could silently encode a different property, such as a GPT-level factorization that does not respect the required operational equivalences. A counterexample would not touch the matrix lemmas but would invalidate the paper's stated problem: deciding whether a theory admits a noncontextual model. This concern is external but foundational: without it, Corollaries 3 and 13 concern the equirank nonnegative rank of a matrix, not generalized contextuality.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The manuscript studies the computational complexity of deciding whether a COPE matrix admits a noncontextual ontological model of a given inner dimension, and of computing the minimal such dimension. Using the rank-separation criterion imported from Ref. [9], the authors reformulate noncontextuality as equirank nonnegative matrix factorization (ENMF), provide a geometric reduction to an intermediate-simplex problem, and derive an upper bound poly(b,m,n)^{O(k^2)} via Moitra's NMF algorithm, together with an ETH-based lower bound (nm)^{Ω(r)} for computing the minimal ontic size. They also present a 5×5 rank-3 COPE matrix for which the minimum noncontextual ontic size is claimed to be 5 while the unconstrained minimum is 4.","tokens_in":27402,"tokens_out":14883,"duration_ms":162714,"significance":"If the central equivalence between noncontextuality and ENMF and the various proof steps were correct, this would be the first nontrivial complexity characterization of generalized contextuality in the COPE/GPT framework, and the explicit separation between NNR and ENNR would be a valuable contribution. The paper has concrete strengths: the example in Section V comes with closed-form factorizations, and Appendix D provides a dual LP certificate for the infeasibility claim. However, because the key equivalence is imported without proof and several load-bearing arguments are incomplete or logically inverted, the significance of the results is currently conditional on substantial revision.","major_comments":[{"comment":"The equivalence between noncontextuality and ENMF is the central premise of the paper, but it is imported from Ref. [9] without proof. Specifically, Lemma 1 and Corollary 2 state that a COPE admits a noncontextual ontological model if and only if it admits an ENMF with rank C = rank R = rank E. All downstream results (Corollary 3, Corollary 13, and Proposition 15) are statements about ENMF existence. If the converse direction of Corollary 2 fails, the paper solves a matrix factorization problem rather than the contextuality problem advertised in the abstract. Because Ref. [9] is a same-author preprint and the present manuscript neither reproduces the proof nor verifies the equivalence independently, the reader cannot check that the results concern generalized contextuality. Please provide a self-contained proof of Corollary 2, or clearly state that the contextuality claims are conditional on the criterion from Ref. [9].","section":"Section II.C"},{"comment":"The dimensions in the statement and proof of Theorem 10 are inconsistent. The theorem statement defines \\bar C as an (m+k-r)×(n+2k-2r) matrix, while the proof constructs \\bar C as the (m+2k-2r)×(n+k-r) slack matrix of \\bar A_b \\bar B_b; the proof also refers to \\bar B_b as an (m+k-r)×k matrix and to \\bar A_b as a k×(n+2k-2r) matrix. These mismatches make the reduction unverifiable as written. More importantly, the forward direction asserts without proof that the vertices of a nested simplex G between \\bar B and \\bar A can be 'rescaled along the h_i directions' to obtain a nested simplex between \\bar B and \\bar A_b. This rescaling is the key step that connects the bounded full-dimensional pair to the original unbounded non-full-dimensional pair, and no rigorous demonstration is given. A complete proof of this equivalence is needed before the reduction can support Corollary 13.","section":"Theorem 10"},{"comment":"The proof of Corollary 7 claims that choosing G = A is without loss of generality because 'Since A is the largest possible nested polytope, such a matrix exists if and only if an ENMF exists.' This monotonicity is not valid: the existence of a rank-r nonnegative matrix mapping the vertices of a smaller nested polytope G to the vertices of B does not imply the existence of such a matrix mapping the vertices of the larger polytope A to B. No extension argument is provided, so the polynomial-time decidability of ENMF existence for fixed rank r, which is stated in the Discussion as a proven result, is not established.","section":"Corollary 7"},{"comment":"The proof excluding all quadrilateral nested polytopes is logically inverted. It states that for any larger polytope G2 containing G1, there is a nonnegative rank-3 matrix E2 = W E1 mapping the vertices of G2 to B_I, where W maps the vertices of G2 to G1. However, a nonnegative W mapping the vertices of a larger polytope into a smaller one cannot exist unless the larger polytope is contained in the smaller one. Lemma 14 gives G1 ⊆ G2, which is the opposite containment. Consequently, the LP infeasibility certificate for the specific hexagon G2 does not rule out maps from all quadrilaterals G1 contained in G2, and the claimed ENNR=5 / NNR=4 separation is not proved.","section":"Section V (Proposition 15)"}],"minor_comments":[{"comment":"The lower bound is written as (nm)^{O(r)} in both the statement and the proof; a lower bound should be (nm)^{Ω(r)}. This notational error should be corrected.","section":"Corollary 3"},{"comment":"The dimensions in the statement of Lemma 6 are inconsistent with the equation GE = B: G is given as k×r and B as m×r, whereas the surrounding usage (Lemma 5 and the proof of Lemma 6) requires G to be r×k and B to be r×n. Please align the conventions.","section":"Lemma 6"},{"comment":"In the proof of Lemma 5, the text introduces R = AF and later writes 'Since R=AG is nonnegative' without defining G at that point; this notation should be harmonized to avoid confusion.","section":"Lemma 5 proof"},{"comment":"Step 2 initializes 'EN ER=0', which appears to be a typo for 'ENNR=0', and step 12 misspells 'algorithm' as 'algroithm'.","section":"Algorithm (Section III)"},{"comment":"The identification of \\bar G with T∘κ and \\bar G^{-1} with T†∘ι is stated as a sketch without derivation; please provide the maps explicitly or label the connection as a conjecture. Also, the citation 'Ref. [19]' for a linear program deciding simplex embeddability points to Craven and Mond (1981), which appears unrelated; please verify the reference.","section":"Section IV"}],"recommendation":"major_revision","confidential_remarks":"The central equivalence of Corollary 2 is taken from a same-author preprint and is not proved in this manuscript; I would ask the editor to require either a self-contained proof or a citation to a published peer-reviewed version. The logical gap in Proposition 15 is particularly serious: even if the example is correct, the current argument does not rule out all quadrilateral nested polytopes. If that gap cannot be repaired, the separation claim should be substantially weakened or removed."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"This paper does three real things: it recasts noncontextuality as equirank nonnegative matrix factorization (ENMF), reduces ENMF existence to an intermediate–simplex question and then to a nonnegative rank decision, and gives an explicit 5-vs-4 ontic-size separation backed by closed-form factorizations and an exact dual LP certificate. The geometric work in Section III is the genuine contribution. Lemma 8’s reduction to a nested simplex is neat, and the construction that fattens the inner and outer polytopes to make them full-dimensional and bounded (Theorem 10) is the right kind of trick. The explicit example in Section V is solid: the factors are explicit, and the nonexistence of a size-4 ENMF is certified by a dual objective value of (7−3√5)/2 > 0, which is a real check.\n\nThe soft spot is where “noncontextual” enters the math. The equivalence between noncontextuality and ENMF is Lemma 1/Corollary 2 of Ref [9], the authors’ own preprint, and this paper does not rederive or independently verify it. That is not automatically a flaw—papers build on prior work—but here the converse direction (ENMF implies a noncontextual model) is exactly where a rank condition could silently encode a different property, such as a GPT-level factorization that does not respect the operational equivalences. If that bridge breaks, the complexity bounds and the size gap are statements about a matrix property, not about contextuality. The same-author dependency makes this foundational rather than cosmetic.\n\nThere are also smaller issues. The statement of Theorem 10 gives dimensions (m+k−r)×(n+2k−2r), while the proof constructs (m+2k−2r)×(n+k−r); that mismatch should be fixed. The paper ships no code or formal verification, but the example is explicit enough for a referee to check by hand.\n\nWho is this for? People working on generalized contextuality, nonnegative rank, or the geometry of GPTs. The ENMF/NNR connection is a useful new tool, and the size-gap example is likely to be cited.\n\nMy recommendation: send it to peer review. The authors should be asked to fix the Theorem 10 dimensions and, more importantly, to either prove the rank-separation criterion or at least make the dependency explicit and include a verification of the converse direction. Without that, the headline complexity results are conditional; with it, the paper is a solid contribution.","headline":"Useful ENMF-based reduction and a credible size-gap example, but the complexity results hinge on an unproved same-author equivalence between contextuality and equirank factorization.","tokens_in":27925,"tokens_out":3424,"would_cite":true,"duration_ms":37960,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q17","15A23","52B11","81P13"],"pacs":[],"model":"deepseek-v4-flash","headline":"Deciding whether a prepare-measure experiment admits a noncontextual model of a given dimension $k$ costs at most $\\mathrm{poly}(b,m,n)^{O(k^2)}$ and, under the Exponential Time Hypothesis, at least $(nm)^{\\Omega(r)}$; the smallest such…","keywords":["generalized contextuality","ontological models","equirank nonnegative matrix factorization","nonnegative rank","intermediate simplex problem","COPE matrix","computational complexity","ontic size"],"falsifier":"Compute the linear program of Lemma 6 for the matrices $G_2$ and $B_I$ defined in Proposition 15: if the optimum objective is exactly zero rather than about $0.146$, then $C_1$ would have an ENMF of inner dimension four, directly contradicting Proposition 15 and the claimed 5-versus-4 gap. Separately, any COPE matrix that admits a generalized-noncontextual ontological model yet violates Corollary 2's rank equality would falsify the rank-separation premise on which all bounds rest.","tokens_in":26950,"feed_emoji":"⚛️","tokens_out":9303,"duration_ms":96951,"temperature":0.7,"pith_summary":"Generalized contextuality marks the boundary between classical and nonclassical explanations of prepare-measure experiments. This paper takes the rank-separation criterion, which identifies a noncontextual ontological model with an equirank nonnegative matrix factorization (ENMF) of the COPE matrix, and turns it into a geometry problem: a noncontextual model of size $k$ exists exactly when a simplex can be sandwiched between two polytopes derived from the data. Using that translation, it proves that deciding existence for a specified $k$ costs at most $\\mathrm{poly}(b,m,n)^{O(k^2)}$ time, and at least $(nm)^{\\Omega(r)}$ under the Exponential Time Hypothesis, so computing the smallest noncontextual model is inefficient in general. It also exhibits an explicit $5\\times5$ rank-3 COPE whose smallest noncontextual model needs five ontic states while its smallest unconstrained ontological model needs only four. The upshot is that a classical explanation is not only computationally costly to find; it is a genuinely different optimization target from merely explaining the statistics.","feed_headline":"Exponential cost to find classical models of quantum data","feed_subtitle":"A 5-by-5 example shows the smallest noncontextual model can exceed the smallest hidden-variable model.","key_machinery":"The central object is the equirank nonnegative matrix factorization (ENMF), a factorization $C=RE$ with nonnegative $R,E$ and equal ranks $\\operatorname{rank} R = \\operatorname{rank} E = \\operatorname{rank} C$; its smallest inner dimension is the equirank nonnegative rank (ENNR), and Corollary 2 equates ENNR with the minimum ontic size of a noncontextual model. The geometric engine is the nested-simplex reformulation (Lemmas 5 and 8): an ENMF of inner dimension $k$ exists exactly when a $(k-1)$-simplex fits between the inner polytope $B$ (the convex hull of epistemic states) and the outer polytope $A$ (the duality-defined set of logically possible states). Theorem 10 converts that sandwich condition into the nonnegative rank of an explicitly constructed slack matrix, and Lemma 6 supplies a polynomial-time linear-programming test for whether a candidate simplex's vertices can be mapped onto $B$ with the correct rank. The size-gap proof uses a pentagon-with-nested-quadrilateral obstruction: Lemma 14 shows no quadrilateral can meet the required five triangular regions, and a dual linear program certifies that the only candidate quadrilateral produces a positive objective, ruling out inner dimension four.","core_discovery":"The paper's central claim is that the equirank nonnegative matrix factorization (ENMF) problem captures generalized noncontextuality: a COPE matrix $C$ with a rank factorization $C=AB$ admits a noncontextual ontological model of inner dimension $k$ if and only if the constructed polytopes $B \\subseteq A$ admit a nested $(k-1)$-simplex $G$ whose vertices can be mapped to the vertices of $B$ by a rank-$r$ nonnegative stochastic matrix. Theorem 10 turns this into a reduction to the nonnegative rank problem: one builds a larger nonnegative matrix whose nonnegative rank equals $k$ exactly when such a simplex exists. Composing that reduction with a known almost-optimal nonnegative-rank decision algorithm gives the upper bound $\\mathrm{poly}(b,m,n)^{O(k^2)}$ for deciding noncontextual models of dimension $k$, while Corollary 3, assuming the Exponential Time Hypothesis, gives a lower bound of $(nm)^{\\Omega(r)}$ for computing the size of the smallest such model. The paper also proves the two optimization problems are different by constructing a $5\\times5$ rank-3 COPE whose equirank nonnegative rank is 5 while its nonnegative rank is 4, with explicit factorizations for both.","pith_inferences":["If the rank-separation equivalence is correct, the reduction works in the opposite direction too: any faster algorithm for nonnegative rank would immediately give a faster search over noncontextual model sizes, and any hardness proof for ENNR would transfer to a hardness proof for NNR on the constructed matrices.","The size gap between ENNR and NNR suggests a quantitative measure: the difference $\\operatorname{ENNR}(C)-\\operatorname{NNR}(C)$, whenever a noncontextual model exists, could serve as a resource quantifier for contextuality in operational theories, with the paper's $C_1$ as a minimal witness.","The polynomial fixed-rank result depends on vertex enumeration of the outer polytope; for structured generalized probabilistic theories whose state spaces are simplexes or simple polytopes, one could exploit those structures to make ENNR computation practically efficient even when rank is not fixed.","A direct test of the paper's conjecture that contextuality detection is computationally hard would be to search for families of COPE matrices for which the constructed nonnegative-rank instances in Theorem 10 are themselves hard for the nonnegative rank problem."],"forward_implications":["For COPE matrices of fixed rank $r$, deciding whether any noncontextual model exists becomes polynomial in $m,n$ and bit length $b$; the hardness appears only when the model dimension $k$ is allowed to grow.","For general rank, the decision problem for dimension $k$ is solvable in $\\mathrm{poly}(b,m,n)^{O(k^2)}$ time, so any exponential dependence on the model size is a genuine barrier, and computing the ENNR rather than deciding a single $k$ is inefficient in the worst case.","The explicit COPE $C_1$ shows $\\operatorname{ENNR}(C_1)=5$ while $\\operatorname{NNR}(C_1)=4$, so the smallest noncontextual model and the smallest ordinary ontological model differ, and results about one cannot be read as results about the other.","Because every ENNR is at most $O(r^2)$ for rank $r$, the gap between the minimal GPT dimension and the smallest noncontextual ontic dimension is polynomially bounded, limiting the advantage a noncontextually explainable protocol can display."],"supporting_citations":[{"why":"Introduces the COPE formalism and the rank-separation criterion (Lemma 1 and Corollary 2) that equates noncontextuality with an equirank nonnegative factorization, the premise all complexity bounds rest on.","marker":"[9]"},{"why":"Supplies the almost-optimal nonnegative-rank decision algorithm whose $\\mathrm{poly}(b,m,n)^{O(k^2)}$ runtime gives the upper bound in Corollary 13.","marker":"[21]"},{"why":"Proves the equivalence between nonnegative rank and the intermediate simplex problem and its NP-hardness, the link Theorem 10 exploits to reduce ENMF to NNR.","marker":"[22]"},{"why":"Provides the lower bound on deciding nonnegative rank that Corollary 3 converts into the $(nm)^{\\Omega(r)}$ lower bound under the Exponential Time Hypothesis.","marker":"[25]"},{"why":"Formulates the Exponential Time Hypothesis used to turn the nonnegative-rank lower bound into a conditional hardness statement for the smallest noncontextual model.","marker":"[26]"},{"why":"Defines generalized noncontextuality, the operational notion whose decidability and model-size complexity the paper studies.","marker":"[3]"}],"fun_headline_variants":["Exponential complexity for deciding noncontextual models","Smallest noncontextual model not always smallest ontological","Deciding contextuality: exponential in theory dimension and k","5x5 example: noncontextual size 5 vs hidden-variable size 4"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that a COPE admits a noncontextual ontological model if and only if it admits an equirank nonnegative matrix factorization, a criterion imported from an earlier paper by the same authors and not rederived here; if that equivalence fails for some operational theories, the complexity results describe a matrix property rather than generalized contextuality.","fun_headline_variants_meta":{"raw":{"variants":["Exponential complexity for deciding noncontextual models","Smallest noncontextual model not always smallest ontological","Deciding contextuality: exponential in theory dimension and k","5x5 example: noncontextual size 5 vs hidden-variable size 4"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000269,"raw_usage":{"total_tokens":1643,"prompt_tokens":989,"completion_tokens":654,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":605,"completion_tokens_details":{"reasoning_tokens":584}},"tokens_in":605,"tokens_out":654,"duration_ms":7621,"temperature":1.0,"reasoning_tokens":584,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T04:58:55.229434+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Compute the linear program of Lemma 6 for the matrices $G_2$ and $B_I$ defined in Proposition 15: if the optimum objective is exactly zero rather than about $0.146$, then $C_1$ would have an ENMF of inner dimension four, directly contradicting Proposition 15 and the claimed 5-versus-4 gap. Separately, any COPE matrix that admits a generalized-noncontextual ontological model yet violates Corollary 2's rank equality would falsify the rank-separation premise on which all bounds rest.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the almost-optimal nonnegative-rank decision algorithm whose $\\mathrm{poly}(b,m,n)^{O(k^2)}$ runtime gives the upper bound in Corollary 13."},{"cited_title":"Craven and B","cited_arxiv_id":null,"evidence_quote":"Proves the equivalence between nonnegative rank and the intermediate simplex problem and its NP-hardness, the link Theorem 10 exploits to reduce ENMF to NNR."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the lower bound on deciding nonnegative rank that Corollary 3 converts into the $(nm)^{\\Omega(r)}$ lower bound under the Exponential Time Hypothesis."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines generalized noncontextuality, the operational notion whose decidability and model-size complexity the paper studies."}],"review_version":1}