{"id":"b1099b60-70e0-4bbf-97cd-f4d7f45dbd2a","arxiv_id":"2508.11515","paper_version":1,"verdict":"UNVERDICTED","confidence":"LOW","novelty_score":7.0,"correctness_risk":"unknown","formal_verification":"none","parameter_count":0,"one_line_summary":"WFOMC is #P1-hard for FO^2 with two linear orders or two acyclic relations, but polynomial for C^2 with a linear order and two successor relations.","lead":"This paper studies the complexity of weighted first-order model counting for two-variable logic when axioms are imposed on two relations at once, rather than one. It proves two new hardness results and one polynomial-time algorithm, extending the known boundary between tractable and intractable counting fragments.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified; full text corrupted, proof unverifiable.","rationale":"The reader's verdict is UNVERDICTED due to the corrupted full text, and I agree that the proof is unverifiable from the available material. I do not identify a specific technical flaw in the abstract's claims: the hardness results are plausible standard gadget reductions, and the positive result is consistent with fixed-language transfer-matrix counting over locally constrained successor relations. I therefore do not manufacture a speculative failure mode. The primary issue is lack of evidence, not a demonstrated error. Since the reader already placed the verdict as UNVERDICTED, no adjustment is needed.","tokens_in":2233,"tokens_out":11593,"duration_ms":154317,"concrete_test":"Obtain a readable copy of the full text and check whether the polynomial-time algorithm for C^2 with a linear order and two successor relations is based on a finite-state/transfer-matrix decomposition of the two successor relations; verify the base cases and the polynomial bound in the proof.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Given only the abstract, no concrete flaw in the central claims is identifiable. The claimed boundary—hard for FO^2 with two linear orders or two acyclic relations, tractable for C^2 with a linear order plus its successor and a second successor—is internally consistent with prior work, and the tractability claim is plausible because two-variable counting with fixed local transition constraints can be handled by transfer-matrix methods. However, the supplied full text is unreadable (mojibake), so no proof of the algorithm or the reductions can be checked. The absence of a demonstrated decomposition for the positive result is a missing-support limitation, not a demonstrated error.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":2381,"tokens_out":3708,"duration_ms":40209,"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":[{"comment":"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.","section":"Full Text (entire manuscript)"},{"comment":"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.","section":"Abstract"}],"minor_comments":[{"comment":"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.","section":"Abstract"},{"comment":"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.","section":"Abstract"},{"comment":"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.","section":"Abstract"}],"recommendation":"uncertain","confidential_remarks":"The manuscript file as supplied is unreadable due to encoding corruption; I could not examine any equations, proofs, or algorithm details. This is not a substantive evaluation. The editor should ask the authors to resubmit a cleanly encoded PDF before assigning referees. I am unable to determine whether the claims are correct, so I recommend 'uncertain' rather than accept/reject. No concerns about citation patterns or novelty can be assessed in this state."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The abstract makes a clear and genuinely interesting claim: all prior WFOMC work with axioms has focused on a single distinguished relation, and this paper is the first to look at axioms on two relations. The two hardness results—FO^2 with two linear orders, and FO^2 with two acyclic relations, both #P1-hard—sit naturally against the known positive results for single-relation axioms. The tractable case is the more striking part: C^2 with a linear order, its successor relation, and a second unrelated successor relation is claimed to be polynomial in the domain size. That is a plausible boundary and, if proved, a real contribution.\n\nWhat the paper does well, from what I can see, is pose the right question and state a crisp, non-obvious answer. The contrast between intractable FO^2 with two linear orders and tractable C^2 with one linear order plus two successors is exactly the kind of result that sharpens our understanding of counting complexity.\n\nNow the soft spots, and they are real but not accusations. I could not read the full text: it is mojibake. No equations, no reductions, no algorithm analysis are visible. Both the hardness reductions and the polynomial-time algorithm are load-bearing and completely unverifiable from the abstract. The positive result especially rests on a structural decomposition that is not even sketched. That is a missing-support limitation, not a demonstrated error. I agree with the stress-test note: the claims are internally consistent and I found no concrete flaw in the abstract's logic, but I have no way to know whether the proofs actually go through.\n\nWho should read this? Anyone working on weighted model counting, two-variable logic, or transfer-matrix style counting arguments. The question is properly placed in the literature, and the answer, if correct, would influence where people look for tractable fragments.\n\nRecommendation: this deserves a serious referee, not a desk reject. Send it out with the full text intact and ask a referee who knows FO^2 counting and reductions to check the two hardness proofs and the decomposition behind the C^2 algorithm. If it checks out, it is a solid paper; if the decomposition fails or the reductions have a gap, it should come back for major revision. But the abstract alone is enough to justify referee time.","headline":"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.","tokens_in":721,"tokens_out":736,"would_cite":false,"duration_ms":25468,"reading_group":"maybe","serious_thinker":"unclear","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["03B70","03C13","68Q17","68Q25"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["weighted first-order model counting","two-variable logic","counting quantifiers","#P1-hardness","linear order axiom","acyclicity axiom","successor relation","lifted inference"],"falsifier":"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.","tokens_in":2213,"feed_emoji":"🔢","tokens_out":5771,"duration_ms":66393,"temperature":0.7,"pith_summary":"Weighted first-order model counting (WFOMC) sums, over all models of a sentence on a finite domain, the product of relation weights. Previous work drew the tractability frontier for two-variable logic by adding a single axiom, such as a linear order or acyclicity, on one distinguished relation. This paper asks what happens when axioms are imposed on two relations at once. It shows that WFOMC for $\\mathsf{FO}^2$ with two linear order relations, and for $\\mathsf{FO}^2$ with two acyclic relations, is $\\mathsf{\\#P_1}$-hard; and it gives a polynomial-in-domain-size algorithm for WFOMC for $\\mathsf{C}^2$ with one linear order, its successor relation, and an additional successor relation. The result matters because it moves the known boundary from single-relation axioms to multiple-relation axioms, revealing both a new hardness barrier and a new tractable fragment.","feed_headline":"Adding a second order axiom makes model counting #P1-hard","feed_subtitle":"A counting-logic fragment with one linear order and two successor relations still counts in polynomial time.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[],"fun_headline_variants":["Two order axioms make FO2 counting #P1-hard","Two acyclic relations: FO2 counting is #P1-hard","Counting with two orders is hard, but one order plus two successors is easy","Tractable counting for C2 with one order and two successors","FO2 counting hard with two orders; C2 counting easy with two successors"],"cache_read_input_tokens":2816,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Two order axioms make FO2 counting #P1-hard","Two acyclic relations: FO2 counting is #P1-hard","Counting with two orders is hard, but one order plus two successors is easy","Tractable counting for C2 with one order and two successors","FO2 counting hard with two orders; C2 counting easy with two successors"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000578,"raw_usage":{"total_tokens":2591,"prompt_tokens":800,"completion_tokens":1791,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":544,"completion_tokens_details":{"reasoning_tokens":1709}},"tokens_in":544,"tokens_out":1791,"duration_ms":14612,"temperature":1.0,"reasoning_tokens":1709,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-05T19:50:37.411175+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[],"review_version":1}