REVIEW 2 major objections 3 minor 1 cited by
Weighted First Order Model Counting for Two-variable Logic with Axioms on Two Relations
T0 review · 2 major / 3 minor · reviewed 2026-08-05 · deepseek-v4-flash
Pith's one-line read Extending two-variable logic with axioms on two relations produces both #P1-hard fragments and a polynomial-time C^2 fragment with a linear order and two successors.
desk verdict If the claims hold, this is the first sharp boundary for WFOMC with axioms on two relations, but I can't check a single proof from this submission. 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 hardness arguments are gadget reductions: they encode a known $\mathsf{\#P_1}$-hard counting problem into WFOMC instances whose two order or acyclic relations are forced to play the roles of the original problem's structure. The tractability result is an algorithm for $\mathsf{C}^2$ whose input includes a linear order and its successor relation, where the successor relation is the immediate-neighbour relation of the linear order, plus a second successor relation. The algorithm exploits the rigid structure imposed by a linear order together with successor relations to decompose the weighted count over the domain into pieces that can be evaluated in polynomial time.
What would settle it
Run the claimed algorithm against brute-force enumeration of weighted models for all $\mathsf{C}^2$ sentences up to a fixed quantifier depth over the vocabulary of one linear order, its successor, and a second successor, on domains of size $n=1,\dots,10$; any mismatch in the exact weighted sum falsifies the polynomial algorithm.
Extended reading notes
Core claim
The paper's central claim is a pair of complementary statements. On the hard side, even the two-variable fragment $\mathsf{FO}^2$ becomes $\mathsf{\#P_1}$-hard when its vocabulary is required to contain two binary relations that are each linear orders, and likewise when the two relations are each required to be acyclic. Thus no polynomial-time WFOMC algorithm can cover these axiom pairs under standard complexity assumptions. On the tractable side, WFOMC for $\mathsf{C}^2$, the two-variable logic with counting quantifiers, remains computable in time polynomial in the domain size when the sentence is evaluated over a linear order, its successor relation, and one additional successor relation.
Load-bearing premise
Both sides of the dichotomy rest on unstated technical machinery: the hardness reductions must encode the source $\mathsf{\#P_1}$-hard problem using only two order or acyclic relations, and the polynomial algorithm's decomposition must cover every sentence in its stated fragment.
Editorial extensions
If this is right
- If the hardness results are correct, there is no polynomial-time WFOMC algorithm for the full two-variable fragment with two linear order axioms; the tractability boundary lies between one and two order relations.
- The positive result identifies a concrete fragment—$\mathsf{C}^2$ with a linear order, its successor relation, and a further successor relation—for which WFOMC can be solved in time polynomial in the domain size.
- Together the results show that the extra latitude of WFOMC is not unlimited: adding axioms to a second relation can break tractability even when the underlying logic is $\mathsf{FO}^2$.
- For applications that use WFOMC as an inference engine, the paper supplies a new class of constraints on two relations that remains exactly countable in polynomial time, while warning that two independent acyclic or order constraints can be too expressive.
Reading between the lines
- A natural open question the paper leaves implicit is the complexity of $\mathsf{FO}^2$ with one linear order and one acyclic relation; if that fragment is also hard, the hardness is driven by mixing two different structural axioms rather than by doubling the same axiom.
- The polynomial fragment suggests an automata-theoretic or transfer-matrix treatment: with a linear order and its successor, the domain is a path, and a second successor relation adds bounded-range edges; a testable extension would be whether replacing the second successor by a bounded-distance relation preserves polynomial time.
- A reader might draw the broader moral that classifying all pairs of axioms will require a finite catalogue of 'hard axiom pairs', analogous to the one-relation dichotomy, with the two-order and two-acyclicity cases as the first entries.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies the Weighted First-Order Model Counting Problem (WFOMC) for two-variable fragments of first-order logic when axioms are imposed on two relations simultaneously. It claims two negative results—WFOMC for FO^2 with two linear order relations is #P1-hard, and WFOMC for FO^2 with two acyclic relations is #P1-hard—and one positive result: an algorithm polynomial in the domain size for WFOMC of C^2 (the two-variable fragment with counting quantifiers) extended by a linear order, its successor relation, and another successor relation. The supplied full text is corrupted and unreadable (mojibake); the assessment below is therefore based almost entirely on the abstract.
Significance. If the claims are correct, the paper fills a genuine gap in the WFOMC literature, which has so far focused on axioms on a single relation. The simultaneous treatment of two relations is a natural and nontrivial extension, and the proposed boundary—hard for two linear orders or two acyclic relations, yet tractable for a linear order plus two successor relations—is internally plausible and consistent with prior results on single-relation axioms. The positive result would be the most valuable contribution, as it suggests that certain combinations of two successor-type axioms still admit symmetry-based or transfer-matrix counting. However, the paper as supplied contains no machine-checked proofs, no code, and no readable technical content, so none of these contributions can currently be verified.
major comments (2)
- [Full Text (entire manuscript)] The supplied full text is corrupted (mojibake) and contains no readable equations, proofs, or algorithm descriptions. As a result, the three central claims—#P1-hardness of FO^2 with two linear orders, #P1-hardness of FO^2 with two acyclic relations, and the polynomial-time algorithm for C^2 with a linear order plus two successor relations—cannot be verified. Since these claims rest entirely on the unreadable technical sections, this is a load-bearing missing support rather than a presentation issue. A readable version of the manuscript is required before any substantive review can proceed.
- [Abstract] Even confining attention to the abstract, the positive result is under-specified: the sentence "we provide an algorithm in time polynomial in the domain size for WFOMC of C^2 with a linear order relation, its successor relation and another successor relation" does not indicate the structural decomposition or algorithmic technique used. The reader cannot assess whether the algorithm is correct, whether it applies to all sentences in the fragment, or whether it generalizes the known single-relation methods. Similarly, the hardness claims mention no reduction source or gadget construction. These are not objections to the claims themselves, but they are missing support that must be supplied in a readable manuscript.
minor comments (3)
- [Abstract] The notation C^2 and FO^2 is used without definitions; readers outside the subfield may not know that C^2 is the two-variable fragment with counting quantifiers.
- [Abstract] The phrase "two acyclic relations" is ambiguous: does it mean each relation is acyclic individually, or that the combined structure forms a directed acyclic graph? Clarification would help.
- [Abstract] The phrase "its successor relation and another successor relation" should specify whether the second successor relation is on the same underlying order or on a second, independent order; this is essential for understanding the claimed tractable fragment.
Circularity Check
No circularity identified; claims are complexity-theoretic with no fitted inputs or self-referential definitions.
full rationale
The paper's central claims are WFOMC hardness results and a polynomial-time algorithm for a C^2 fragment with a linear order and two successor relations. These are complexity-theoretic theorems based on reductions and algorithm design; the abstract does not fit any parameter to data, define the target in terms of its own output, or rename a known result. The supplied full text is largely unreadable due to encoding corruption, so no specific equation, proof step, or self-citation chain could be inspected. However, under Rule 1, circularity must be exhibited by quoting the paper and showing a specific reduction (e.g., Eq. X = Eq. Y by construction, or fitted parameter renamed as prediction). No such reduction is available or identifiable from the abstract alone. The reader's summary notes that the proofs are unverifiable from the abstract, but unverifiability is a correctness-risk concern, not circularity. No passage in the readable text asserts a limitation, missing support, or self-referential definition. Therefore the score is 0: no significant circularity found.
Assumptions & free parameters
assumptions (1)
- standard math Standard definitions and hardness classes of WFOMC and #P1
Cite this review
Pith. "Pith review of Weighted First Order Model Counting for Two-variable Logic with Axioms on Two Relations." pith.science (2026). https://pith.science/paper/IGVQM6EU
@misc{pith2026250811515,
author = {Pith},
title = {Pith review of: Weighted First Order Model Counting for Two-variable Logic with Axioms on Two Relations},
year = {2026},
howpublished = {\url{https://pith.science/paper/IGVQM6EU}},
note = {Machine review of arXiv:2508.11515}
}
abstract
The Weighted First-Order Model Counting Problem (WFOMC) asks to compute the weighted sum of models of a given first-order logic sentence over a given domain. The boundary between fragments for which WFOMC can be computed in polynomial time relative to the domain size lies between the two-variable fragment ($\text{FO}^2$) and the three-variable fragment ($\text{FO}^3$). It is known that WFOMC for \FOthree{} is $\mathsf{\#P_1}$-hard while polynomial-time algorithms exist for computing WFOMC for $\text{FO}^2$ and $\text{C}^2$, possibly extended by certain axioms such as the linear order axiom, the acyclicity axiom, and the connectedness axiom. All existing research has concentrated on extending the fragment with axioms on a single distinguished relation, leaving a gap in understanding the complexity boundary of axioms on multiple relations. In this study, we explore the extension of the two-variable fragment by axioms on two relations, presenting both negative and positive results. We show that WFOMC for $\text{FO}^2$ with two linear order relations and $\text{FO}^2$ with two acyclic relations are $\mathsf{\#P_1}$-hard. Conversely, we provide an algorithm in time polynomial in the domain size for WFOMC of $\text{C}^2$ with a linear order relation, its successor relation and another successor relation.
Forward citations
Cited by 1 Pith paper
-
DiCriTest: Testing Scenario Generation for Decision-Making Agents Considering Diversity and Criticality
The abstract claims a dual-space framework, DiCriTest, improves critical scenario generation by 56.23%, but the attached full text is an unrelated logic paper, leaving the claim unverifiable.
Reference graph
Works this paper leans on
-
[1]
���� ���������� ������ ������ � ������������������ ������ ������� ����� �� ���� ������� ��� �������������� ����� ���� ���� ������ �� �������� ������� ��� ����������� ������� �������� ���������� ������� ��� ���������� �� ����� ���� ������ ��� �������� ������������ ��� ���������� �� ��� ���� � ��������� ������������ �� ��������������� �������� �� ��������� ...
work page Pith review arXiv 2025
Reviewed August 5, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.