REVIEW 3 major objections 3 minor
Approximating 1-in-3 SAT by linearly ordered hypergraph 3-colouring is NP-hard
T0 review · 3 major / 3 minor · reviewed 2026-08-05 · deepseek-v4-flash
Pith's one-line read 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.
desk verdict 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. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
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.
What would settle it
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.
Extended reading notes
Core claim
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
Load-bearing premise
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.
Editorial extensions
If this is right
- 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.
Reading between the lines
- 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.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
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.
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 (3)
- [Abstract, central claim] 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.
- [Abstract, methodology] 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.
- [Abstract, easy consequence] 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.
minor comments (3)
- [Abstract, terminology] 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.
- [Abstract, related work] The abstract mentions 'several recent papers' and 'Filakovský et al.' without bibliographic details. A complete submission should include references.
- [Abstract, novelty claim] 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.
Circularity Check
No circularity found: the abstract presents an independent NP-hardness proof with no fitted inputs, self-citation chains, or definitional equivalences.
full rationale
The abstract claims NP-hardness of a specific Promise CSP (linearly ordered 3-colouring of 3-uniform hypergraphs) using the algebraic approach via polymorphism analysis. No step in the abstract defines a target quantity in terms of itself, nor does it fit a parameter to data and then rename that fit as a prediction. The folklore conjecture is mentioned only as context ('as predicted by the conjecture'), not as a load-bearing assumption; the proof is described as combinatorial and independent. The 'easy consequence' matching Filakovsk\'y et al. is cited as a separate prior result, not as evidence for the present claim. Since the full text is unavailable, we cannot check the unstated polymorphism classification lemma or the gap-preserving property, but absence of evidence is not evidence of circularity. There are no self-citations in the abstract, no uniqueness theorems imported from the authors' prior work, and no ansatz smuggled in via citation. Thus the derivation chain, as presented, is not circular: the NP-hardness reduction is claimed to be proved from the polymorphism analysis rather than assumed. Score 0 is appropriate because no circular step can be quoted or exhibited from the available text.
Assumptions & free parameters
assumptions (2)
- standard math Borsuk-Ulam theorem and standard homotopy classification results
- domain assumption The algebraic approach to Promise CSP complexity via polymorphism analysis is valid
Cite this review
Pith. "Pith review of Approximating 1-in-3 SAT by linearly ordered hypergraph 3-colouring is NP-hard." pith.science (2026). https://pith.science/paper/LITOT3CU
@misc{pith2026250814606,
author = {Pith},
title = {Pith review of: Approximating 1-in-3 SAT by linearly ordered hypergraph 3-colouring is NP-hard},
year = {2026},
howpublished = {\url{https://pith.science/paper/LITOT3CU}},
note = {Machine review of arXiv:2508.14606}
}
abstract
Given a satisfiable instance of 1-in-3 SAT, it is NP-hard to find a satisfying assignment for it, but it may be possible to efficiently find a solution subject to a weaker (not necessarily Boolean) predicate than `1-in-3'. There is a folklore conjecture predicting which choices of weaker predicates lead to tractability and for which the task remains \NP-hard. One specific predicate, corresponding to the problem of linearly ordered $3$-colouring of 3-uniform hypergraphs, has been mentioned in several recent papers as an obstacle to further progress in proving this conjecture. We prove that the problem for this predicate is NP-hard, as predicted by the conjecture. We use the Promise CSP framework, where the complexity analysis is performed via the algebraic approach, by studying the structure of polymorphisms, which are multidimensional invariants of the problem at hand. The analysis of polymorphisms is in general a highly non-trivial task, and topological combinatorics was recently discovered to provide a useful tool for this. There are two distinct ways in which it was used: one is based on variations of the Borsuk-Ulam theorem, and the other aims to classify polymorphisms up to certain reconfigurations (homotopy). Our proof, whilst combinatorial in nature, shows that our problem is the first example where the features behind the two uses of topology appear together. Thus, it is likely to be useful in guiding further development of the topological method aimed at classifying Promise CSPs. An easy consequence of our result is the hardness of another specific Promise CSP, which was recently proved by Filakovsk\'y et al. by employing a deep topological analysis of polymorphisms.
Reviewed August 5, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.