{"id":"d4a16409-c9c0-4c59-9332-6180ff4ba64b","arxiv_id":"2508.14606","paper_version":1,"verdict":"UNVERDICTED","confidence":"LOW","novelty_score":8.0,"correctness_risk":"unknown","formal_verification":"none","parameter_count":0,"one_line_summary":"Finding a linearly ordered 3-colouring for a 1-in-3 SAT instance that is known to be satisfiable is NP-hard.","lead":"This paper proves that a naturally relaxed form of 1-in-3 SAT, phrased as ordering a hypergraph's vertices with three colors, is NP-hard even when a perfect solution is guaranteed to exist. The result resolves a known gap in the theory of promise constraint satisfaction, a field that classifies which approximate versions of hard problems remain hard.","discovery_kind":"first_principles","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Central NP-hardness claim is unverifiable from abstract alone; proof hinges on an unstated polymorphism classification lemma whose homotopy-based argument must be exact.","rationale":"The reader correctly identified the polymorphism-structure lemma as the weakest assumption, and the verdict UNVERDICTED is appropriate because the full proof is unavailable. I agree partially: the more precise concern is whether the homotopy classification is strong enough to support the algebraic NP-hardness proof, and whether the gadget reduction preserves the exact promise gap. The abstract alone gives no evidence on these points. However, I do not see a definitive flaw; the claim is plausible and consistent with the Promise CSP framework. Therefore the correct outcome is to keep the reader's UNVERDICTED status rather than escalate to rejection or acceptance. The concrete test is to check the two conditions directly in the full text.","tokens_in":785,"tokens_out":1980,"duration_ms":28429,"concrete_test":"Obtain the full manuscript and verify the two load-bearing conditions: (1) The key lemma classifying polymorphisms of the linearly ordered 3-colouring predicate is exact and covers all finite arities, not just a homotopy class that could omit or add relevant polymorphisms. (2) The reduction from 1-in-3 SAT to the promise problem is gap-preserving: for every unsatisfiable 1-in-3 SAT instance, the constructed hypergraph has no linearly ordered 3-colouring. If either fails, the NP-hardness proof collapses. If both hold, the central claim stands.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim is the NP-hardness of the promise problem mapping satisfiable 1-in-3 SAT instances to linearly ordered 3-colourable hypergraphs. The abstract states the proof uses the algebraic approach via a classification of polymorphisms, specifically exploiting two topological tools: Borsuk-Ulam-type arguments and classification of polymorphisms up to homotopy. The weakest load-bearing premise is that this homotopy classification is complete and exact for the linearly ordered 3-colouring predicate. In Promise CSP topology, classifying polymorphisms only up to homotopy can be insufficient: a homotopy-equivalent family may miss finitary polymorphisms that would provide a tractability algorithm, or may include spurious polymorphisms that invalidate an NP-hardness reduction. The proof also needs the reduction from 1-in-3 SAT to be gap-preserving: every unsatisfiable 1-in-3 SAT instance must yield a hypergraph with no linearly ordered 3-colouring, not merely one whose colourings lack certain homotopy properties. Because the full text is unavailable, neither the classification lemma nor the reduction's gap property can be checked. This is not an internal inconsistency, but an unresolved, load-bearing gap in the argument as presented.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper claims to prove that the promise problem of finding a linearly ordered 3-colouring of a 3-uniform hypergraph, given that the corresponding 1-in-3 SAT instance is satisfiable, is NP-hard. This is presented as a step toward the folklore conjecture that predicts which weaker predicates make such search problems tractable or intractable. The proof is said to use the Promise CSP algebraic approach, combining topological tools of the Borsuk-Ulam type with classification of polymorphisms up to homotopy. The paper further claims an easy consequence: the hardness of another specific Promise CSP recently proved by Filakovský et al. The full text was not available to the referee; only the abstract was reviewed.","tokens_in":1072,"tokens_out":2165,"duration_ms":26722,"significance":"If the proof is correct, this resolves a concrete obstacle that several recent papers identified in the classification of Promise CSPs, and it would be the first example showing that the two topological techniques (Borsuk-Ulam and homotopy classification) can be combined in a single NP-hardness proof. This is potentially a significant methodological contribution to the algebraic approach for Promise CSPs. The claimed easy consequence would also unify or re-derive a recent deep result. However, because the submitted material is only the abstract, none of these claims can be independently verified.","major_comments":[{"comment":"The abstract asserts NP-hardness of the promise problem, but does not specify the reduction from 1-in-3 SAT. A load-bearing requirement is that every unsatisfiable 1-in-3 SAT instance maps to a hypergraph with no linearly ordered 3-colouring (soundness/gap). Without stating this, or providing a citation to a full proof, the NP-hardness claim is not established in the material available. The lack of reduction details prevents verification.","section":"Abstract, central claim"},{"comment":"The proof is said to rely on 'classification of polymorphisms up to homotopy.' As the stress-test note correctly observes, homotopy classification can be insufficient for exact NP-hardness: a homotopy-equivalent family may miss or add finitary polymorphisms that affect the reduction. The abstract offers no justification for why homotopy-level information suffices here. This is a load-bearing premise that must be explicitly addressed in the full paper; the abstract alone leaves the correctness of the proof uncertain.","section":"Abstract, methodology"},{"comment":"The abstract claims that a specific result of Filakovský et al. follows as an 'easy consequence,' but gives no derivation or citation. While this is a secondary claim, it is presented as part of the paper's contribution. At minimum, a precise statement and a sketch (or citation) are needed; as written, the claim is unverifiable.","section":"Abstract, easy consequence"}],"minor_comments":[{"comment":"The term 'linearly ordered 3-colouring' is not defined in the abstract. Even for a specialist audience, a one-sentence definition would help. Similarly, 'Promise CSP' and 'polymorphism' are used without definition, though these are standard in the area.","section":"Abstract, terminology"},{"comment":"The abstract mentions 'several recent papers' and 'Filakovský et al.' without bibliographic details. A complete submission should include references.","section":"Abstract, related work"},{"comment":"The phrase 'first example where the features behind the two uses of topology appear together' is a novelty assertion. It may be true, but it should be substantiated in the introduction by contrasting with prior examples.","section":"Abstract, novelty claim"}],"recommendation":"uncertain","confidential_remarks":"The review is based solely on the abstract; the full text was not made available. This is an unusual situation for a referee report. The abstract alone is insufficient to determine correctness of the proof or to recommend acceptance. The stress-test concern about homotopy classification is real and must be addressed. If the full text is available, I would need to see the reduction and the polymorphism classification lemma before making a definitive recommendation."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things to know. First, the paper takes a concrete step on a known open problem in Promise CSP: the linearly ordered 3-colouring predicate has been flagged as an obstacle, and the paper claims to remove it by proving NP-hardness. Second, the proof is genuinely inaccessible from the abstract, so any verdict beyond plausible is not honest. The reader's UNVERDICTED score is right.\n\nWhat is new: the claimed result is new, and the method is a first combination of two topological polymorphism tools: Borsuk-Ulam-type arguments and homotopy classification. If the proof holds, this is a real contribution. The easy consequence recovering Filakovský et al. is a useful sanity check. The abstract is coherent and no circularity is apparent.\n\nSoft spots: the only thing I can critique is what is missing. The abstract does not sketch the polymorphism classification lemma or the reduction's gap property. The stress-test note raises a legitimate concern: classifying polymorphisms up to homotopy may not automatically give an exact classification, and the reduction needs unsatisfiable instances to produce hypergraphs with no linearly ordered 3-colouring, not merely ones lacking homotopy features. I cannot say that concern lands because the full text is unavailable. It is a reason to read the full proof carefully, not a reason to doubt the result.\n\nWho is this for? Researchers working on Promise CSP, topological combinatorics, algebraic methods. A serious referee should get the full paper. My recommendation: send to peer review and ask the referee to verify the polymorphism classification lemma and the gap-preserving reduction explicitly. If those hold, this is a solid step forward.","headline":"Plausible and important new NP-hardness result for a specific Promise CSP obstacle, but abstract-only access means the proof cannot yet be assessed; still deserves peer review.","tokens_in":565,"tokens_out":1118,"would_cite":false,"duration_ms":19580,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"Finding a linearly ordered 3-colouring of a 3-uniform hypergraph is NP-hard even when a 1-in-3 SAT solution is known to exist.","keywords":["promise CSP","1-in-3 SAT","linearly ordered 3-colouring","3-uniform hypergraph","NP-hardness","polymorphisms","Borsuk-Ulam","homotopy"],"falsifier":"Find a 3-uniform hypergraph that is 1-in-3-satisfiable but admits no linearly ordered 3-colouring, which would invalidate the promise; or give a polynomial-time algorithm that on all such hypergraphs outputs an ordered 3-colouring, which would contradict NP-hardness (assuming P≠NP). A more targeted check is to examine the claimed polymorphism classification for a missing polymorphism that the reduction does not eliminate.","tokens_in":770,"feed_emoji":"🧩","tokens_out":38786,"duration_ms":466686,"temperature":0.7,"pith_summary":"This paper proves that a specific way of weakening 1-in-3 SAT is still NP-hard: given a hypergraph (each edge a triple) that is promised to have an assignment making exactly one vertex true in every edge, it is NP-hard to find an assignment satisfying the weaker 'linearly ordered 3-colouring' predicate. This matters because this predicate was the main known obstruction to a folklore classification of which promise relaxations of 1-in-3 SAT are tractable and which are hard. The proof operates in the Promise CSP framework and studies the polymorphism clone of the target predicate, combining two topological techniques that had previously been used separately. If the result is right, no polynomial-time algorithm can solve this promise problem unless P=NP, and the classification conjecture's prediction for this predicate is confirmed.","feed_headline":"Ordered 3-colouring stays NP-hard with a 1-in-3 promise","feed_subtitle":"Finding the weaker ordered colouring is as hard as solving the original SAT problem, unless P=NP.","key_machinery":"The linearly ordered 3-colouring predicate — the ternary target relation over a three-element linearly ordered set that weakens 'exactly one true'. The argument is carried by the algebraic promise-CSP method: the complexity is controlled by the polymorphism clone of this predicate, i.e., the set of multi-argument functions that preserve the relation. The paper's contribution is a combinatorial analysis of this clone that shows both Borsuk-Ulam-type obstructions and homotopy-theoretic reconfigurations appear simultaneously in one problem; the reduction from 1-in-3 SAT uses that analysis to force the promised structure onto the target colours.","core_discovery":"The paper's central claim is that the promise problem with target the linearly ordered 3-colouring of 3-uniform hypergraphs is NP-hard. Concretely, it asserts that there is no polynomial-time algorithm that, given a 3-uniform hypergraph known to admit a 1-in-3 SAT assignment, outputs a colouring of its vertices with the ordered three-element predicate; any such algorithm would allow a polynomial-time solution of all NP problems. The proof is algebraic: it analyzes the multidimensional symmetry invariants (polymorphisms) of the target predicate and uses topological combinatorics, specifically in a way that for the first time brings together Borsuk-Ulam-type arguments and a homotopy-based clas","pith_inferences":["The same style of argument may extend to linearly ordered k-colourings for larger k, suggesting a family of NP-hard promise problems parameterised by the size of the ordered colour set.","If the polymorphism classification in the proof is robust, then any target predicate that is a homomorphic relaxation of this one should also be NP-hard; this could resolve additional cases of the conjecture.","A concrete way to test the reach of the techniques is to attempt the analogous reduction for the unordered NAE 3-colouring target; the paper's abstract indicates that hardness there already follows, so the new material is the ordered structure rather than the colouring aspect alone."],"forward_implications":["The folklore conjecture's prediction for this predicate is verified: the promise problem is NP-hard, so it cannot be solved in polynomial time unless P=NP.","The target predicate is no longer an open obstacle in the classification of promise CSPs; any dichotomy theorem must place it on the hard side.","The proof supplies a concrete example where Borsuk-Ulam-type and homotopy-based polymorphism analyses interact, giving a template for future classifications.","Another promise CSP whose hardness was known from a deep topological argument now follows as an easy corollary of this result."],"supporting_citations":[],"fun_headline_variants":["1-in-3 promise fails to ease ordered 3-colouring","Ordered 3-colouring NP-hard under 1-in-3 promise","NP-hard even with 1-in-3 promise: ordered hypergraph colouring","Promising 1-in-3 SAT doesn't make ordered colouring tractable"],"cache_read_input_tokens":2688,"weakest_assumption_plain":"The proof depends on an unstated combinatorial lemma characterising the polymorphism clone of the linearly ordered 3-colouring predicate (up to homotopy); if that classification is wrong, the reduction from 1-in-3 SAT could fail to be sound.","fun_headline_variants_meta":{"raw":{"variants":["1-in-3 promise fails to ease ordered 3-colouring","Ordered 3-colouring NP-hard under 1-in-3 promise","NP-hard even with 1-in-3 promise: ordered hypergraph colouring","Promising 1-in-3 SAT doesn't make ordered colouring tractable"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000798,"raw_usage":{"total_tokens":3399,"prompt_tokens":847,"completion_tokens":2552,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":591,"completion_tokens_details":{"reasoning_tokens":2469}},"tokens_in":591,"tokens_out":2552,"duration_ms":18932,"temperature":1.0,"reasoning_tokens":2469,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-05T18:23:03.093335+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Find a 3-uniform hypergraph that is 1-in-3-satisfiable but admits no linearly ordered 3-colouring, which would invalidate the promise; or give a polynomial-time algorithm that on all such hypergraphs outputs an ordered 3-colouring, which would contradict NP-hardness (assuming P≠NP). A more targeted check is to examine the claimed polymorphism classification for a missing polymorphism that the reduction does not eliminate.","supporting_citations":[],"review_version":1}