Pith. sign in

REVIEW 4 major objections 6 minor 1 cited by

The $\text{FP}^\text{NP}$ versus #P dichotomy for #EO

T0 review · 4 major / 6 minor · reviewed 2026-08-09 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read The paper proves that every #EO problem—counting weighted Eulerian orientations—is either #P-hard or computable in polynomial time with a single NP oracle, with an explicit algebraic criterion separating the two cases.

desk verdict First full FP^NP vs #P dichotomy for #EO is claimed, but the proof omits Case 4 of Theorem 28 and is vague about the RAM model; still worth serious refereeing. read the letter →

arxiv 2502.02012 v2 pith:XKDK2AIU submitted 2025-02-04 cs.CC

Boning Meng , Juqiu Wang , Mingji Xia This is my paper · ORCID
classification cs.CC MSC 68Q1568Q1705C30
keywords complexitydichotomycountingHolantproblemEulerianorientation#PFP^NPEOsignaturesupportidentification
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper claims to settle the complexity of #EO, the problem of counting weighted Eulerian orientations of a graph. For every finite set $F$ of Eulerian-orientation signatures, the paper proves that $\#\mathrm{EO}(F)$ is either #P-hard or computable in polynomial time with a single NP oracle, and gives an explicit algebraic condition that decides which. The condition is stated in terms of the bitwise sum of support strings and two tractable classes of signatures, EOA and EOP. If true, this closes the last of the five intermediate problems that have stood between partial results and a full dichotomy for the Holant framework, and it yields three further dichotomies for related signature families.

What carries the argument

Three objects carry the argument. First, the pinning signature $\Delta = \ne^{1,0}_2$, which fixes one variable to 0 and another to 1; a generating process using gadgets and polynomial interpolation realizes $\Delta$ from almost any signature set unless the set already has the ARS property. Second, the bitwise-addition criterion $\oplus$ on support strings: a signature with three support strings whose bitwise sum leaves the support is an $\exists_3$ signature and forces #P-hardness, while $\forall_3$ closure makes effective supports affine and therefore tractable. Third, the classes EOA and EOP, defined by requiring every restriction of a signature to each pairing pattern to lie in the #CSP tractable classes A or P; these are exactly the tractable families, and in the non-rebalancing tractable case an NP oracle decides which support strings are effective before a polynomial algorithm for A or P is run.

What would settle it

Go to the omitted Case 4 in the proof of Theorem 28 and look for a finite set $F$ of EO signatures in which every signature is $\forall_3$ but $F$ is not contained in EOA or EOP; if $\#\mathrm{EO}_c(F)$ turned out not to be #P-hard, or if a set inside EOA/EOP that is neither 0-rebalancing nor 1-rebalancing defeated the claimed $\mathrm{FP}^{\mathrm{NP}}$ algorithm, the dichotomy would be false.

Watch

Extended reading notes

Core claim

The central claim is Theorem 26: for any finite set $F$ of EO signatures, $\#\mathrm{EO}(F)$ is #P-hard unless every signature in $F$ is a $\forall_3$ signature or every signature is a $\bar{\forall}_3$ signature, and $F \subseteq \mathrm{EOA}$ or $F \subseteq \mathrm{EOP}$; in exactly those cases the problem lies in $\mathrm{FP}^{\mathrm{NP}}$. Within the tractable case, the paper further claims the problem is polynomial-time computable unless $F$ is neither 0-rebalancing nor 1-rebalancing, in which case the algorithm needs one NP oracle to identify which support strings are effective. The $\forall_3$ condition says that the bitwise sum of any three support strings is again a support string with balanced weight, and the EOA/EOP conditions say that every restriction of a signature to a pairwise-opposite pattern belongs to the #CSP tractable classes A or P. This is presented as the first complete complexity classification of complex #EO, the last remaining intermediate problem on the route toward a Holant dichotomy.

Load-bearing premise

The proof of the pinned dichotomy explicitly omits one case, saying it is 'similar' to another; the whole classification depends on that omitted case being the exact mirror image and on the mirror argument preserving the tractability criteria and reductions.

Editorial extensions

If this is right

  • Every #EO problem now has a complete complexity classification: no signature set falls between #P-hardness and $\mathrm{FP}^{\mathrm{NP}}$ unless the dichotomy itself fails.
  • The NP oracle is needed only in the non-rebalancing tractable case; all other tractable cases are claimed to be polynomial-time computable.
  • The dichotomy extends to $\mathrm{Holant}(\ne_2 | F)$ for $\mathrm{HW}_{\geq}$, $\mathrm{HW}_{\leq}$, and single-weighted signature sets, giving three new $\mathrm{FP}^{\mathrm{NP}}$ versus #P dichotomies.
  • The result covers and subsumes earlier partial classifications for the six-vertex model, signatures with the ARS property, and pure signatures.
  • A full FP versus #P dichotomy for #EO would follow if the support-identification problem were classified; the present result stands as $\mathrm{FP}^{\mathrm{NP}}$ versus #P unless that happens.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • If the dichotomy is right, the last of the five intermediate problems named in the Holant research program is settled, so the remaining route to a full Holant dichotomy is to connect these intermediate classifications through holographic transformations.
  • The open support-identification problem is essentially a Boolean constraint satisfaction problem; a dichotomy for it would upgrade the $\mathrm{FP}^{\mathrm{NP}}$ result to FP versus #P and is the natural next target.
  • The bitwise-addition criterion resembles affine-support criteria in #CSP, so one could test whether a similar $\forall_3$-style criterion governs other Holant fragments with vanishing signatures.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

4 major / 6 minor

Summary. The paper claims a full FPNP vs #P dichotomy for complex-weighted Eulerian orientation counting (#EO). For a finite signature set F, #EO(F) is declared #P-hard unless all signatures in F are ∀3 or all are ∀3 signatures and F ⊆ EOA or F ⊆ EOP, in which case it lies in FPNP; an additional P-time clause is given under 0/1-rebalancing. The proof proceeds by reducing #EOc(F) = #EO(F ∪ {Δ}) to #EO(F) (Section 4), proving a dichotomy for #EOc via a four-case support analysis (Section 5), and then extending the result to HW≥, HW≤, and single-weighted signatures (Section 6). Along the way the paper introduces a support-identification oracle and identifies it as the main obstacle to an FP vs #P dichotomy.

Significance. If the theorem is completed, this is a major step for the Holant program: it subsumes and extends the earlier ARS, six-vertex, and pure-signature dichotomies, and it supplies an explicit algebraic criterion that could drive the full Holant classification. The paper is also honest about its limitations, explicitly flagging the open support-identification problem and the f56 obstruction to an FP version. However, the current manuscript leaves load-bearing gaps: the ∀3 case is omitted from the central case analysis, one key lemma in the FPNP algorithm contains a sign/balance error, and the infinite-roots reduction in Section 4.3 is argued in a nonstandard computation model. These are repairable, but they must be fixed before the theorem as stated is proven.

major comments (4)
  1. [Section 5, Case 4] The proof of Theorem 28 partitions into four cases and then states: 'We omit the analysis of Case 4 as it is similar to that of Case 3.' Case 4 covers signature sets in which all signatures are ∀3, an alternative that appears explicitly in the criterion of Theorem 26; the omission is therefore load-bearing. The duality with Case 3 under bitwise complement is plausible, but the manuscript does not supply the dual versions of Lemmas 60–66. In particular, Lemma 65's '0-moving step' argument is not obviously symmetric under complementation, and the printed proof of Lemma 60 contains a sign error (see the next comment). As written, Theorem 28 does not establish the dichotomy for pure-down and other ∀3-only signature sets.
  2. [Section 5.4, Lemma 60] The line 'For RHS, all signatures in F are ∀3 signatures, so δ′∈ HW≥' is not a consequence of Definition 25: a ∀3 signature forbids δ∈HW> and also forbids a missing δ∈HW=, but it explicitly allows δ∈HW<. The desired contradiction can be recovered by the argument that no RHS block δ_i lies in HW>, while the global balance from the LHS ≠2 constraints then forces every δ_i to lie in HW=. But as printed, Lemma 60 and the subsequent Lemma 61, on which the FPNP algorithm of Lemma 55 depends, are not proved. Please rewrite this argument in a way that uses the actual definition of ∀3.
  3. [Section 4.3, infinitely many roots] The reduction for the infinitely-many-roots case is not carried out in the standard Turing model. The text first says that for algebraic weights a finite extension field avoids infinitely many roots and that 'further discussion within this subsection becomes unnecessary,' but Theorem 26 is stated for complex-valued signatures. It then invokes a 'Complex RAM' model in which operations such as logarithm are single computational steps. Since Theorem 27's second alternative, and hence Theorem 26, depends on this reduction, the paper must either restrict the dichotomy to algebraic inputs with a precise representation and complexity account, or give a standard Turing-machine implementation of the generation bounds and interpolation step.
  4. [Section 4.4.1, Lemma 40] The acknowledgments state that a mistake in Lemma 40 was pointed out in an early version, but the current proof still needs a careful rewrite. The induction begins 'Without loss of generality, suppose α=100δ, β=010δ, γ=001δ are three strings with Hamming weight d' without establishing that these three strings all lie in supp(f) or that the displayed values are nonzero. Since Lemma 40 feeds directly into Lemma 42 and hence into the ARS-ignoring-a-constant conclusion used in Theorem 27, a clean and fully justified proof is required.
minor comments (6)
  1. [Definition 25] The phrase 'neither a ∃3↛ signature nor a ∃3↑ signature (or a ∃3↓ signature)' should explicitly state that ∀3 and ∀3 are two separate properties; as written it can be misread as a single condition with an optional clause.
  2. [Section 2.1] There is a typo: 'Now we provides a formal definition' should read 'Now we provide a formal definition.'
  3. [Section 5] Please label the case list as cases 1–4 with subcases 3a–3d in the running text; the current formatting makes it easy to confuse the omitted Case 4 with subcase 3d.
  4. [Section 6.2, Corollary 68] In Step 4 of the reduction, the instruction 'connect it to an introduced Δ1 via a ≠2 signature on LHS' should specify how the introduced Δ0 and Δ1 signatures are paired and why the resulting components are guaranteed to be balanced; the current sentence relies on a counting statement that appears only later in the paragraph.
  5. [Footnote 1] The footnote about first-author status and score-sharing schemes is not relevant to the technical content and should be removed.
  6. [Section 7] The sentence 'the issue addressed in this article is not yet encompassed by extant research' is vague; please specify what class of Boolean constraint satisfaction problems the support-identification instances form and how they relate to the classification in [13].

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the #EO dichotomy is built from external #CSP/#EO dichotomies and internal gadget reductions; the admitted omitted Case 4 is a completeness gap, not a circular step.

full rationale

The claimed derivation chain is not circular. Theorem 26 is reduced to Theorem 27 (proved in Section 4 by interpolation and gadget constructions) and Theorem 28 (Section 5). The tractable direction is Lemma 55: it replaces each signature by its effective support using an NP oracle and then invokes the external #CSP algorithms for A/P. The hardness direction uses external dichotomy theorems (#CSP Theorem 12, ARS Theorem 18, pure-signature Theorem 22, six-vertex Theorems 16 and 17) and internal lemmas (49, 54, 63-66). No parameter is fitted to the conclusion, and no tractability criterion is defined as whatever the algorithm can solve; the ∀3/∀3 and EOA/EOP conditions are independent algebraic/support conditions proved separately to imply tractability or hardness. Two caveats are correctness/completeness concerns rather than circularity. First, Section 5 explicitly states: 'We omit the analysis of Case 4 as it is similar to that of Case 3,' so the written proof of Theorem 28 leaves a dual case unproved. Second, Lemma 60 as printed contains the direction 'δ′∈HW≥' which appears to be a sign typo; the valid argument should conclude that each RHS block is not in HW> and global LHS balance forces HW=. These issues affect the completeness of the case analysis, but they do not make any theorem equivalent to its own assumptions. The same-author citations (Theorems 22 and 24 from [18]) are parameter-free external theorems whose stated assumptions do not include the target dichotomy, so under the review rules they count as independent support and do not raise the circularity score.

Assumptions & free parameters 0 free parameters · 7 assumptions · 0 invented entities

The central claim rests on previously established dichotomy theorems for #CSP, arity-limited EO, ARS, and pure signatures, all cited. No free parameters or invented entities are introduced.

assumptions (7)
  • domain assumption Dichotomy for complex weighted Boolean #CSP (Theorem 12 of [12])
    Invoked for #P-hardness in Lemma 64 and in the EOM-connection Theorem 14, underpinning the hardness side of the dichotomy.
  • domain assumption Dichotomy for the six-vertex model / quaternary EO signatures (Theorem 16 of [9])
    Used in Lemmas 45 and 46 to restrict the support size of arity-4 signatures in the finite-roots case.
  • domain assumption Dichotomy for EO signatures of arity at most 4 (Theorem 17 of [18])
    Used in Lemma 51 to establish #P-hardness for the small-arity base case of the ∃3↛ argument.
  • domain assumption ARS dichotomy for #EO (Theorem 18 of [8])
    Used in the proof of Theorem 26, Case 1, when the signature set reduces to ARS-ignoring-a-constant.
  • domain assumption Pure signatures dichotomy (Theorem 22 of [18])
    Used for Case 3a of the #EOc dichotomy (pure-up signatures).
  • domain assumption Rebalancing P-time algorithm (Theorem 24 of [18])
    Provides the polynomial-time base cases in Theorem 26 and supports the FP^NP algorithm for rebalancing signatures.
  • domain assumption Support identification problem is in NP (Definition 58 and discussion)
    The FP^NP algorithm calls an NP oracle for this problem; its exact complexity is left open.

how reviews work

0 comments
Cite this review

Pith. "Pith review of The $\text{FP}^\text{NP}$ versus #P dichotomy for #EO." pith.science (2026). https://pith.science/paper/XKDK2AIU

@misc{pith2026250202012,
  author       = {Pith},
  title        = {Pith review of: The $\textFP^\textNP$ versus #P dichotomy for #EO},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/XKDK2AIU}},
  note         = {Machine review of arXiv:2502.02012}
}
abstract

The complexity classification of the Holant problem has remained unresolved for the past fifteen years. Counting complex-weighted Eulerian orientation problems, denoted as #EO, is regarded as one of the most significant challenges to the comprehensive complexity classification of the Holant problem. This article presents an $\text{FP}^\text{NP}$ vs. #P dichotomy for #EO, demonstrating that #EO defined by a signature set is either #P-hard or polynomial-time computable with a specific NP oracle. This result provides a comprehensive complexity classification for #EO, and potentially leads to a dichotomy for the Holant problem. Furthermore, we derive three additional dichotomies related to the Holant problem from the dichotomy for #EO.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. From an odd arity signature to a Holant dichotomy

    cs.CC 2025-02 conditional novelty 8.0 of 10

    Complex-valued Holant with a non-trivial odd-arity signature is classified: every instance is either #P-hard or in FPNP.

Reference graph

Works this paper leans on

28 extracted references · 24 canonical work pages · cited by 1 Pith paper

  1. [1]

    Computational complexity: a modern approach

    Sanjeev Arora and Boaz Barak. Computational complexity: a modern approach . Cambridge University Press, 2009

    2009

  2. [2]

    A complete dichotomy for complex-valued Holant^c

    Miriam Backens. A complete dichotomy for complex-valued Holant ^ c . arXiv preprint arXiv:1704.05798 , 2017

    work page Pith review arXiv 2017

  3. [3]

    Between the stochastic six vertex model and hall-littlewood processes

    Alexei Borodin, Alexey Bufetov, and Michael Wheeler. Between the stochastic six vertex model and hall-littlewood processes. arXiv preprint arXiv:1611.09486 , 2016

    arXiv 2016

  4. [4]

    Stochastic six-vertex model

    Alexei Borodin, Ivan Corwin, and Vadim Gorin. Stochastic six-vertex model. 2016

    work page 2016

  5. [5]

    Proofs and confirmations: the story of the alternating-sign matrix conjecture

    David M Bressoud. Proofs and confirmations: the story of the alternating-sign matrix conjecture . Cambridge University Press, 1999

    work page 1999

  6. [6]

    Complexity dichotomies for counting problems: Volume 1, Boolean domain

    Jin-Yi Cai and Xi Chen. Complexity dichotomies for counting problems: Volume 1, Boolean domain . Cambridge University Press, 2017

    work page 2017

  7. [7]

    Complexity classification of the eight-vertex model

    Jin-Yi Cai and Zhiguo Fu. Complexity classification of the eight-vertex model. Information and Computation , 293:105064, 2023

    work page 2023

  8. [8]

    Beyond \# CSP : A dichotomy for counting weighted Eulerian orientations with ARS

    Jin-Yi Cai, Zhiguo Fu, and Shuai Shao. Beyond \# CSP : A dichotomy for counting weighted Eulerian orientations with ARS . Information and Computation , 275:104589, 2020

    work page 2020

Show all 28 references
  1. [9]

    Complexity classification of the six-vertex model

    Jin-Yi Cai, Zhiguo Fu, and Mingji Xia. Complexity classification of the six-vertex model. Information and Computation , 259:130--141, 2018

    2018

  2. [10]

    A complete dichotomy rises from the capture of vanishing signatures

    Jin-Yi Cai, Heng Guo, and Tyson Williams. A complete dichotomy rises from the capture of vanishing signatures. In Proceedings of the forty-fifth annual ACM symposium on Theory of computing , pages 635--644, 2013

    2013

  3. [11]

    Holant problems and counting CSP

    Jin-Yi Cai, Pinyan Lu, and Mingji Xia. Holant problems and counting CSP . In Proceedings of the forty-first annual ACM symposium on Theory of computing , pages 715--724, 2009

    2009

  4. [12]

    The complexity of complex weighted Boolean \# CSP

    Jin-Yi Cai, Pinyan Lu, and Mingji Xia. The complexity of complex weighted Boolean \# CSP . Journal of Computer and System Sciences , 80(1):217--236, 2014

    2014

  5. [13]

    Classification of bipartite boolean constraint satisfaction through delta-matroid intersection

    Tom \'a s Feder and Daniel Ford. Classification of bipartite boolean constraint satisfaction through delta-matroid intersection. SIAM Journal on Discrete Mathematics , 20(2):372--394, 2006

    2006

  6. [14]

    Calculation of norms of bethe wave functions

    Vladimir E Korepin. Calculation of norms of bethe wave functions. Communications in Mathematical Physics , 86:391--418, 1982

    1982

  7. [15]

    Another proof of the alternative-sign matrix conjecture

    Greg Kuperberg. Another proof of the alternative-sign matrix conjecture. International Mathematics Research Notices , 1996(3):139--150, 1996

    1996

  8. [16]

    Residual entropy of square ice

    Elliott H Lieb. Residual entropy of square ice. Physical Review , 162(1):162, 1967

    1967

  9. [17]

    The complexity of Boolean Holant problems with nonnegative weights

    Jiabao Lin and Hanpin Wang. The complexity of Boolean Holant problems with nonnegative weights. SIAM Journal on Computing , 47(3):798--828, 2018

    2018

  10. [18]

    P-time algorithms for typical \# EO problems

    Boning Meng, Juqiu Wang, and Mingji Xia. P-time algorithms for typical \# EO problems. arXiv preprint arXiv:2410.11557 , 2024

    2024 arXiv

  11. [19]

    On the number of eulerian orientations of a graph

    Milena Mihail and Peter Winkler. On the number of eulerian orientations of a graph. Algorithmica , 16:402--414, 1996

    1996

  12. [20]

    Alternating sign matrices and descending plane partitions

    William H Mills, David P Robbins, and Howard Rumsey Jr. Alternating sign matrices and descending plane partitions. Journal of Combinatorial Theory, Series A , 34(3):340--359, 1983

    1983

  13. [21]

    Stochastic higher spin six vertex model and q-taseps

    Daniel Orr and Leonid Petrov. Stochastic higher spin six vertex model and q-taseps. Advances in Mathematics , 317:473--525, 2017

    2017

  14. [22]

    The structure and entropy of ice and of other crystals with some randomness of atomic arrangement

    Linus Pauling. The structure and entropy of ice and of other crystals with some randomness of atomic arrangement. Journal of the American Chemical Society , 57(12):2680--2684, 1935

    1935

  15. [23]

    Computational geometry: an introduction

    Franco P Preparata and Michael I Shamos. Computational geometry: an introduction . Springer Science & Business Media, 2012

    2012

  16. [24]

    Über ein zweidimensionales klassisches konfigurationsmodell

    Franz Rys. Über ein zweidimensionales klassisches konfigurationsmodell. In Helvetica Physica Acta , volume 36, page 537. Birkhauser Verlag AG VIADUKSTRASSE 40-44, PO BOX 133, CH-4010 BASEL, SWITZERLAND, 1963

    1963

  17. [25]

    A dichotomy for real Boolean Holant problems

    Shuai Shao and Jin-Yi Cai. A dichotomy for real Boolean Holant problems. In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS) , pages 1091--1102. IEEE, 2020

    2020

  18. [26]

    Eulerian orientations and Hadamard codes: A novel connection via counting

    Shuai Shao and Zhuxiao Tang. Eulerian orientations and Hadamard codes: A novel connection via counting. arXiv preprint arXiv:2411.02612 , 2024

    2024 arXiv

  19. [27]

    Theory of the transition in kh2po4

    John C Slater. Theory of the transition in kh2po4. The Journal of Chemical Physics , 9(1):16--33, 1941

    1941

  20. [28]

    Proof of the alternating sign matrix conjecture

    Doron Zeilberger. Proof of the alternating sign matrix conjecture. arXiv preprint math/9407211 , 1994

    1994 arXiv

Pith tools

Reviewed August 9, 2026 · model on record in the stance chip above.