| paper | d4-conf-aaai-2004-0008 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
other→P discrete result → its continuous mirror
Answer: polynomial-time solvable · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 1
statement extracted from the paper’s text layer
Given request types \(T\) with rational population masses \(\mu_t\), a priority order on types, integral configurations \(Q_t\) satisfying each type’s request, resource vectors \(a(q)\), and per-capita shared capacities \(b\), find a feasible allocation \(z_{tq}\ge 0\) with \(y_t=\sum_{q\in Q_t}z_{tq}\le\mu_t\) and \(\sum_{t,q}a(q)z_{tq}\le b\), whose retained-mass vector \(y\) is lexicographically greatest in the priority order.
A large configuration service with many users from a finite set of complete request types. Each user receives an integral configuration, while each type’s cohort may be split across configurations; \(y_t\) is the mass whose requests are retained, and shared per-capita capacities scale with the population.
The mirror specializes the paper’s solver-independent constraint problem to grouped user requests under shared capacities, and type masses may not preserve richer interactions between constraints.
fatal: False
The mirror covers preferred relaxation and its connection to preferred conflicts in configuration settings; it leaves the generic solver-independent QUICKXPLAIN method, multiple preferred explanations, and search-engineering results aside.
My strongest honest mirror is a population version of the preferred relaxation that QuickXplain computes through its preferred-conflict procedure. The paper’s best named anchor is Theorem 1, proved here. It says that QUICKXPLAIN always terminates; when \(B\cup C\) is consistent, it returns “no conflict”; otherwise it returns a preferred conflict of \((B,C,\prec)\). For a partial order, “preferred” means preferred under some linearization of \(\prec\), as in the paper’s definition. The theorem establishes correctness and termination, not a complexity class: the paper has no named theorem saying this problem is in P or is hard.
A plausible regime is a large product-configuring service, fleet procurement, or infrastructure plan serving many people whose requests come from a small catalogue of recurring profiles. A type \(t\) records the complete request and priority information, as well as any per-user costs or parameters the model uses. The population is \(\mu\) over types, with \(\tau\) recurring profiles and many more than \(\tau\) people. Shared budgets or capacities scale with the population. Each person still receives an integral configuration; the mass assigned to a configuration can be fractional because a type’s cohort can be split.
Here is the prover-ready question. Call it Mass-Preferred Relaxation. An instance gives a finite type set \(T\), rational masses \(\mu_t\) summing to one, a strict priority order on types, and a configuration model. For each type \(t\), the model describes its finite set \(Q_t\) of integral configurations that satisfy that type’s request. Each configuration \(q\) has a resource vector \(a(q)\), and the shared background gives aggregate capacities \(b\). Find masses \(z_{tq}\ge 0\) and retained masses \(y_t\) such that
\[
y_t=\sum_{q\in Q_t}z_{tq}\le\mu_t,\qquad
\sum_{t\in T}\sum_{q\in Q_t} a(q)z_{tq}\le b,
\]
and \(y\) is lexicographically greatest in the given priority order. Return \(y\) and an allocation \(z\) witnessing feasibility. The removed mass \(\mu_t-y_t\) says how much of each type’s request must be relaxed. This is the population counterpart of keeping the preferred requirements that can jointly be satisfied; the paper itself motivates that dual view of conflicts and relaxations.
I expect Class A for configuration families whose implicit \(Q_t\) have polynomial-time pricing: the retained masses and allocation form a continuous optimization problem, and lexicographic priorities can be handled by successive optimization. With compact but hard configuration descriptions, pricing may instead carry the difficulty. That is the right follow-up question, not a claim that Theorem 1 already answers it: can the exact preferred mass vector be found in time polynomial in the configuration encoding size, \(\tau\), and the rational input length? Further questions include whether the resulting allocation has a polynomial-size certificate and what additive guarantees it gives for a discrete population with integer cohort counts.
This mirror covers the preferred conflict/relaxation computation, not the paper’s full discussion of explanation algorithms, multiple preferred explanations, or solver engineering. Its weak point is that the paper studies constraints on one configuration problem, often one customer’s, whereas this scenario adds shared population-scaled capacities and permits a cohort to be split across integral configurations. That is a substantial model co-modification. I think it is plausible for large-scale configuration and procurement, and the paper’s problem of choosing preferred requirements under infeasibility remains visible in it; still, the authors might regard it as a useful adjacent problem rather than their direct continuous analogue.
The strongest objection is that Theorem 1 is a correctness-and-termination result for a finite set of constraints, not a complexity classification for a population problem. QUICKXPLAIN repeatedly adds or removes whole constraints and asks a consistency oracle whether the remaining set has a solution. The paper does analyze oracle calls and reports polynomial response time for polynomial CSPs, but that generic algorithm has no population axis to continueize.
That matters because the objects being grouped here are constraints, not agents. In an arbitrary CSP, a constraint’s role depends on the variables it touches and how those variables interact with the rest of the instance. Grouping constraints by their written form can lose that structure; including their full neighborhoods can leave almost every constraint in a different type. If the constraints are exact duplicates, their multiplicity is often logically redundant. There is no general reason their mass should behave like the mass of interchangeable people.
The proposed mass model is coherent, but it adds a particular population problem: recurring user requests, integral configurations for each user, and shared capacities that scale with the cohort. Its \(y_t\) measures how much of each cohort can be served. QUICKXPLAIN instead returns a preferred, irreducible set of constraints explaining why one CSP is inconsistent. The new model’s answer is an allocation or rejection rate, not such an explanation. Shared capacities and split cohorts make the model workable, but they are substantive structure introduced to create a population problem; they do not follow from the paper’s generic CSP formulation.
The strongest way to repair the connection is to take many copies of a configuration module, with recurring request types and common resource limits. If modules interact only through additive capacities, this gives a sensible high-multiplicity relaxation. But that special case is a configuration allocation problem: the key algorithmic question becomes how to price or describe each type’s configurations. If modules have richer cross-links, type masses alone generally do not preserve consistency. Either way, the result is no longer a continuous version of QUICKXPLAIN’s solver-independent preferred-conflict computation.
That defeats the direct anchor as a mirror of the paper’s named result. It does not defeat every worthwhile research question suggested by the paper. A large service or procurement system with repeated requests and shared capacity is plausible, and its continuous preferred-retention problem could be worth studying. I cannot honestly rule out that the authors would recognize it as a useful extension. The negative case is strongest on the mismatch between the paper’s generic constraint-explanation problem and the added cohort-allocation model; it is weak as a universal claim that no worthwhile continuous mirror exists in any scenario.
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.