| paper | d4-conf-aaai-2008-0083 |
| 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: Solvable in deterministic polynomial time in the binary input length. · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Theorem 2
Given a finite object set \(U\) and a finite support \(T\) with rational masses \(\mu_t>0\) and \(\sum_{t\in T}\mu_t=1\), where each type \(t\) carries an explicitly represented finite strict partial order \(\succ_t\) and a \(k\)-layer contractor \(CON_t\subseteq\succ_t\), compute for every \(t\) an inclusion-minimal \(P^-_t\) satisfying \(CON_t\subseteq P^-_t\subseteq\succ_t\) such that \(\succ_t\setminus P^-_t\) is a strict partial order. Every unit of mass of type \(t\) receives the same contraction.
A continuous cohort distribution \(\mu\) over complete user types, each carrying an explicit finite preference relation and contraction request; choose one minimal contractor per type and apply it to that type’s mass by running Algorithm 1 independently for each support type.
The mass is computationally inert, so the population version decomposes into independent contractions for each support type; this limits its population-level content.
fatal: False
The mirror covers Theorem 2’s minimal contraction and, with protected preferences in each type, Theorem 4’s protected variant. It leaves the contraction characterizations, query-optimization results, and complexity of formula-represented infinite relations outside the finite explicit mirror.
The strongest honest mirror is a continuous cohort version of preference contraction. Imagine a large product platform with millions of users, but only \(\tau\) distinct learned preference models and contraction requests. Users of a type share the same preference relation and the same request to discard preferences. That is a plausible high-multiplicity regime: the population is large, while the number of distinct models is comparatively small.
For the lead problem, Continuous Cohort Minimal Contraction, an instance consists of a finite object set \(U\) and a distribution \(\mu\) over finitely many types \(t\). Each type has positive rational mass \(\mu_t\), a strict partial order \(\succ_t\) over \(U\), and a base contractor \(CON_t\subseteq\succ_t\); require each \(CON_t\) to be \(k\)-layer. The action is to choose a contractor \(P^-_t\) for every type and apply it to that cohort. A valid answer must satisfy \(CON_t\subseteq P^-_t\subseteq\succ_t\), leave \(\succ_t\setminus P^-_t\) a strict partial order, and be inclusion-minimal: no proper subset of \(P^-_t\) is still a contractor. The objective is exactly the paper’s minimality condition, not minimum cardinality or minimum cost. Each member of a cohort receives the same integral contraction; \(\mu_t\) says what fraction of the population that cohort represents.
The anchor is Theorem 2, proved in this paper: for a \(k\)-layer base contractor relation \(CON\), Algorithm 1 returns a minimal full contractor of \(\succ\) by \(CON\) and halts in \(k+1\) iterations. That is precisely the typewise guarantee this mirror asks to compute. For explicit finite relations, the paper also reports an implementation running in \(O(|CON|^2|\succ|\log|\succ|)\), citing a separate 2008 technical report. Applying that finite algorithm to each support type gives a tractable finite-instance mirror, with the total work depending on the sum of the typewise input sizes. The theorem’s iteration guarantee alone does not establish a polynomial bound for the paper’s formula-based infinite-relation setting, where quantifier elimination is used.
A second, richer anchor is Theorem 4, also proved here. It says that if \(CON\) is \(k\)-layer, \(P^+\) is transitive, and \(P^+\cap CON=\varnothing\), Algorithm 2 terminates and returns a full contractor of \(\succ\) by \(CON\) that is minimal with respect to \(CON\) and protects \(P^+\). The corresponding problem, Continuous Cohort Protected Contraction, has the same population input, with a transitive protected relation \(P^+_t\) for each type satisfying those conditions. Its solution is a typewise contractor with \(P^-_t\cap P^+_t=\varnothing\), minimal under the same inclusion criterion. This is a meaningful extension when a platform wants to retire obsolete comparisons while retaining specified preferences. It has the same expected tractability for explicit finite relations and the same open complexity caveat for symbolic infinite relations.
The case for authors’ recognition is that the operation stays intact: each type has their preference relation, its base contractor, and, in the second problem, protected preferences. The only change is that the relation belongs to a large cohort of indistinguishable users. The mass is therefore genuinely population mass, though it does not alter which contractors are valid.
The weakness is substantial: contraction is independent across types, so the masses do not affect the answer, and the paper does not study society-level aggregation or interaction. This is a continuous-population wrapper around a per-user operation, rather than a new fractional optimization problem. The paper also gives no named hardness result to anchor a question about discrete hardness dissolving in the continuum. Its useful follow-up questions are whether the formula-based infinite-relation version admits sharper complexity bounds, and how to choose among multiple minimal contractors if the population has a meaningful aggregate preference for retaining some comparisons.
Theorem 2 and Theorem 4 are real algorithmic anchors, so the negative case cannot claim that this paper has no computational result. The stronger objection is that both algorithms operate on one preference relation and one contraction request at a time. The paper does not make a population-level choice.
Take the most plausible mirror: a platform has many users grouped by identical preference relations and identical contraction requests. For Theorem 2, each group gets a minimal contractor; for Theorem 4, its protected preferences are part of the group’s type too. This is a sensible high-multiplicity scenario, but the mass does no work. A group with mass \(0.1\) gets the same contractor as one with mass \(0.9\). For explicit finite relations, the paper’s reported algorithm can be run once per distinct type; that is useful reuse, but it is batching identical individual operations, not a continuous optimization problem. For symbolic infinite relations, the relation formulas and quantifier elimination still carry the computational burden; adding masses does not change it.
One could try to make mass matter by allowing a cohort to split among several minimal contractors and then maximizing the population’s total retained preferences. But that adds an aggregate objective absent from the paper. Without a shared constraint or policy, the choice still decomposes by type, and the mass merely weights an independent choice. With such a constraint, the task is a new optimization problem: Theorem 2 or 4 may provide feasible contractors, but neither theorem solves the coupled population problem. Treating an average of users’ relations as the object to contract is a different reformulation again; an average need not be a strict partial order, and the paper’s results do not address how to construct or contract one.
The same gap remains if the scenario is reframed as social choice over common alternatives. The paper changes each user’s own preference relation; it does not aggregate users’ preferences into a collective relation or outcome. Adding that collective step could produce a worthwhile research question, but it would not be a continuous mirror of the named results.
So the best case against is that these anchors do not give the continuous population any computational role. The limitation is real: clustered users with shared preference models are plausible, and reuse across a large cohort has value. I cannot honestly rule out every useful extension. But on the evidence of Theorems 2 and 4, that extension would need a new, population-level objective or constraint; the proposed cohort version alone is a wrapper around per-type computation.
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.