| paper | d4-conf-aaai-2025-0010 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
P→P discrete result → its continuous mirror
Answer: Polynomial-time solvable, with a topological ordering returned on every yes-instance. · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Proposition 2
statement extracted from the paper’s text layer
Given \(m\) attributes, \(\tau\) types with positive rational masses \(\mu_t\) summing to \(1\), and a complete CP-theory \(P_t\) for each type, form \(P_\mu=\bigcup_{t:\mu_t>0}P_t\). Under the promise that \(P_\mu\) is locally consistent, decide whether \(H(P_\mu)\) is acyclic and, if so, return a topological ordering.
Types \(t\) are complete CP-theories \(P_t\), and \(\mu_t\) is their population mass. Under the stated mandatory-requirements semantics, pool the supported theories by union; the cc-acyclicity answer depends on support rather than the values of \(\mu_t\).
The population interpretation is specialized: it treats each person's complete CP-theory as mandatory, so even a tiny positive-mass type can veto the pooled theory.
fatal: False
The mirrors cover Proposition 2's cc-acyclicity test and Proposition 4's upper-approximation comparison; Theorem 1 supplies the consistency guarantee behind the test. They leave exact consistency and the top-\(k\) discussion without a separate computational anchor.
My strongest case is a narrow one: the paper’s tractable cc-acyclicity test has a direct high-multiplicity mirror. I would model a large group whose members submit conditional preference rules as mandatory policy requirements. A type is a member’s complete CP-theory over the policy attributes; \(\mu_t\) is the fraction of the population with that theory. The pooled theory is \(P_\mu=\bigcup_{t:\mu_t>0}P_t\), with duplicate statements removed. For example, a public health authority might collect conditional requirements about urgency, waiting time, cost, and equity from millions of patients and advocates, many of whom share a small number \(\tau\) of preference templates. Treating every represented type’s rules as binding makes pooling by union sensible: the question is whether the requirements can fit together, not which preference wins a vote.
Lead mirror — Mass-Profile cc-Acyclicity. Given \(m\) binary attributes, \(\tau\) CP-theory types with positive rational masses summing to \(1\), and their theories \(P_t\), form \(P_\mu\). Given the promise that \(P_\mu\) is locally consistent, decide whether its high-cardinality dependency graph \(H(P_\mu)\) is acyclic; return a topological ordering when it is. This is exactly the computational question in Proposition 2, proved in this paper: given locally consistent preferences \(P\), checking the cc-acyclic sufficient condition can be done in polynomial time. The condition being checked is that \(H(P)\) is acyclic. The result’s value is clear from Theorem 1, also proved here: local consistency together with acyclicity of \(H(P)\) guarantees that \(P\) is consistent. The continuous problem is therefore to recognize, from a population’s supported preference types, when their pooled requirements have this efficiently checkable consistency certificate. It is Class A, with running time polynomial in \(m\), the total number of statements, and the masses’ bit length. For binary attributes, the paper also recalls a polynomial test for local consistency, so that promise can be checked as part of the input procedure.
A second, useful mirror is Mass-Profile cc-Comparison. Use the same population input, promised locally consistent and cc-acyclic, and give two outcomes \(o,o'\). Decide whether \(o\gg_{cc}o'\). In the paper’s definition, \(\Theta(o,o')\) consists of the attributes on which the outcomes differ whose ancestors in the transitive closure of \(H(P_\mu)\) do not differ. For each \(X\in\Theta(o,o')\), \(d(X)_{o,o'}\) combines the values in \(o\) of \(X\)’s ancestors with the unique conditional-parent values used for \(X\) by singleton conditional arcs. The query returns yes exactly when, for every such \(X\), \(o(X)\) is above \(o'(X)\) in the transitive closure of the pooled preferences on \(X\) compatible with \(d(X)_{o,o'}\). Proposition 4, proved here, says that this relation can be computed in polynomial time; the paper gives a bound of \(O(|V|^2|P|^2)\). This is a comparison in the paper’s upper-approximation relation, not a claim that it decides exact dominance. The paper proves that the relation includes every pair of outcomes that is actually related by preference dominance. This mirror is also Class A.
These are not claims that the paper’s whole problem becomes easy in a continuum. The paper’s introduction reports that exact consistency checking is PSPACE-complete even under local consistency or binary domains, citing earlier work; that hardness is not a numbered result of this paper, so it is not one of my anchors. Exact consistency of the pooled \(P_\mu\) is a natural further question. A finite instance embeds by making its statements the supported types and assigning them equal rational masses, so the cited hardness transfers: that version is Class B. The two mirrors above cover the paper’s new tractable certificate and comparison results, not exact consistency, and not the paper’s top-\(k\) discussion as a separate complexity result.
The authors should recognize the mirrors as their problem: after taking the union of supported theories, the formal input is precisely their set \(P\), and the computed condition or relation is precisely theirs. The weak point is that the mass values do not affect either answer once support is fixed. This is a genuine high-multiplicity representation, but the application needs a setting where every represented type’s requirements count, including a small group’s. If the intended setting instead needs majority or weighted preference aggregation, this mirror would change the authors’ question.
The strongest objection is that the paper has no population in its model. Its variables describe attributes of outcomes, and \(P\) is one CP-theory: a set of conditional preference statements that jointly define a dominance relation. Statements have no voter identity, owner, or weight. A population of people submitting CP-theories could be a plausible new setting, but pooling their theories by union adds a unanimity rule: every represented type’s statements become binding.
That makes both proposed anchors insensitive to population mass. For Mass-Profile cc-Acyclicity, any two distributions with the same support produce the same \(P_\mu\), whether a type has mass \(1\%\) or \(99\%\). A type with arbitrarily small positive mass contributes all its statements. Proposition 2 and Theorem 1 then apply directly to the union, but the calculation is over the resulting set \(P_\mu\); the population proportions do no work. Proposition 4 has the same issue: the upper-approximation query is about \(P_\mu\), so it too depends on which theories appear, not how much mass they carry. In this model, the “continuum” records the presence of preference templates rather than their prevalence.
A more population-sensitive version could ask what fraction of people have cc-acyclic theories, or what fraction endorse a given comparison under their own theories. Those are well-defined statistics, but they evaluate each supported theory separately and weight the resulting yes-or-no answers by \(\mu_t\). The propositions provide the per-theory algorithms; the population query adds a weighted sum. That looks like a useful application of the paper’s results, but it does not continuize the paper’s problem of checking one theory.
Making mass affect a collective answer requires choosing additional semantics: for example, a threshold for which statements count, a majority rule over outcome comparisons, or a maximum-mass coalition whose pooled theory is cc-acyclic. The paper supplies no natural way to assign fractional strength to a CP-theory statement; its statements are constraints whose transitive closure defines dominance. A coalition or repair problem could be worth studying, but it adds a population-selection or aggregation problem. It is harder to argue that the paper’s consistency-checking result is itself a mirror of that problem.
This is a relevance argument, not a proof that no useful scenario exists. A large stakeholder group whose requirements are all mandatory would make the union interpretation plausible, and the paper’s results would apply cleanly. If the authors accepted that veto-based setting and considered support alone a sufficient population model, both anchors survive. The negative case is therefore genuinely weak: it can challenge whether these are worthwhile continuous mirrors, but it cannot rule out the authors recognizing one of them as their problem.
The adversarial triple: the proponent anchors on up to three named results; the opponent sees that case and must defeat every anchor; the judge decides which case convinced it. These are the pipeline’s own outputs, generated by tools/triple_run.py — no human edited them. The paper’s own text is not reproduced here beyond the quoted statement above.