| paper | d4-journals-jair-2017-0017 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
NP-hard→NP-hard discrete result → its continuous mirror
Answer: The threshold decision problem is \(\mathrm{NP}\)-hard, even for \(\tau=n=1\) and \(\mu_{t_0}=q=1\). Exact optimization is therefore not polynomial-time solvable unless \(\mathrm{P}=\mathrm{NP}\). Allocation is always feasible under the stated promises. · discrete side: hardness · adjudication: proved_with_minor_gaps
full proof & adversarial review →
Theorem 8
statement extracted from the paper’s text layer
Given a finite set of types \(T\), where each type \(t\) specifies a complete MCS \(M_t\) and preference order \(\preceq_t\), rational masses \(\mu_t\) summing to \(1\), and a target \((t_0,D_0)\), let \(\mathcal A_t=D^{\pm}_{m,\preceq_t}(M_t)\). Choose \(x_{t,D}\ge 0\) for \(D\in\mathcal A_t\), subject to \(\sum_{D\in\mathcal A_t}x_{t,D}=\mu_t\) for each \(t\), and maximize \(x_{t_0,D_0}\), taking it to be \(0\) if \(D_0\notin\mathcal A_{t_0}\); report infeasibility if some \(\mathcal A_t\) is empty.
A society is a distribution \(\mu\) over complete MCS types, each with its own preference order. The decision variable \(x_{t,D}\) is the mass of type \(t\) receiving the integral diagnosis \(D\); maximize the mass receiving a specified preferred diagnosis.
The paper formalizes repair of one integrated MCS, while this question applies repairs to a fleet of separate case systems; that adds a population layer whose relevance to the authors' setting is not established by a theorem.
fatal: False
The mirror covers Theorem 8's preferred-diagnosis membership hardness as the mass attaining a target repair; it leaves the paper's filter encodings, meta-reasoning transformations, and other diagnosis complexity results aside.
The strongest mirror is a fleet of patient-specific hospital information systems. Each patient case is an MCS like the paper’s hospital example: patient data, a treatment recommender, and billing, connected by bridge rules. A type is the full case configuration that matters to diagnosis selection: the context logics and knowledge bases, bridge-rule network, and preference order over diagnoses. Cases of one type are interchangeable in every respect the problem uses. In a large standardized network, millions of cases could fall into a relatively small number \(\tau\) of such configurations. Their mass \(\mu_t\) is the fraction of cases of type \(t\).
I would lead with Continuous Preferred-Diagnosis Allocation. An instance gives a finite set of types \(T\), rational masses \(\mu_t\) summing to \(1\), and, for each \(t\), an MCS \(M_t\) and a reflexive, transitive preference order \(\preceq_t\) on its candidate diagnoses. A diagnosis \(D=(D_1,D_2)\) removes bridge rules in \(D_1\) and makes those in \(D_2\) condition-free. For a target type \(t_0\) and candidate diagnosis \(D_0\), choose nonnegative masses \(x_{t,D}\), one for each diagnosis \(D\) of \(M_t\), to
\[ \max x_{t_0,D_0} \quad\text{subject to}\quad \sum_{D\in\mathcal A_t}x_{t,D}=\mu_t \quad\text{for every }t, \]
where \(\mathcal A_t\) is the set of subset-minimal \(\preceq_t\)-preferred diagnoses of \(M_t\). Here a diagnosis is preferred if no strictly more preferred diagnosis repairs the MCS; it is subset-minimal if no proper pointwise subset is also preferred. A solution is an optimal rational mass profile, or a report that no such profile exists. Each actual case gets a whole diagnosis; fractional \(x_{t,D}\) records the share of indistinguishable cases receiving that diagnosis.
The anchor is Theorem 8, proved in this paper (with its proof in Appendix A.4). The paper defines MCSDMPREF as deciding, given an MCS \(M\), a candidate diagnosis \(D\), and a preference order \(\preceq\), whether \(D\in D^{\pm}_{m,\preceq}(M)\). The theorem states that if \(CC(M)\) is hard for \(\Sigma_i^P\) (respectively, \(\Pi_i^P\)), then MCSDMPREF is hard for \(\Pi_{i+1}^P\) (respectively, \(\Pi_{i+2}^P\)), for \(i\geq 0\). It further states that MCSDMPREF is \(\Pi_2^P\)-hard even when both \(CC(M)\) and the decision of whether \(D'\preceq D''\) hold are in \(P\). The latter clause is my anchor: selecting a minimal preferred repair can be hard even when the contexts and preference comparisons are individually tractable.
The allocation problem mirrors that selection question directly. With one type of mass \(1\), its optimum is \(1\) exactly when the target diagnosis belongs to \(D^{\pm}_{m,\preceq}(M)\), and \(0\) otherwise. So the theorem’s \(\Pi_2^P\)-hardness transfers to this continuous problem, already with polynomial context reasoning and polynomial-time preference comparison. I expect hardness transfers, not tractability: the difficult combinatorics lie in the system’s bridge rules and preferred-diagnosis relation, rather than in how many copies of a case exist. A natural complexity report would track \(\tau\), the MCS sizes, and the bit length \(L\) of the masses and preference descriptions.
This seems plausible as an analogue of the authors’ problem because the paper is about choosing repairs for inconsistent systems, and its motivating hospital setting already describes patient data and treatment decisions. The population is the collection of case systems; the mirror leaves each case’s repair discrete and aggregates only how many cases of each complete type receive each repair. That makes the mass a meaningful operational quantity: a hospital network can ask what fraction of cases can receive a particular approved repair.
The weak point is that the paper does not couple repairs across cases. Without an added fleet-level constraint, the allocation decomposes by type; the continuum compresses repeated cases, but it does not change the inner preferred-diagnosis computation or create a new algorithmic advantage. That limits the claim to a credible high-multiplicity version of the paper’s repair-selection problem. It does not support a broader claim that continuization makes this paper’s hardness disappear.
Theorem 8 is a real anchor: it is a named computational result, and its \(\Pi_2^P\)-hardness clause holds even with tractable context reasoning and preference comparisons. The objection is to the proposed continuous problem, not to the theorem.
As written, its allocation constraints separate by type and add no population-level decision. Assuming each \(\mathcal A_t\) is nonempty, the optimum is simply
\[ \max x_{t_0,D_0} = \begin{cases} \mu_{t_0}, & D_0 \in \mathcal A_{t_0},\\ 0, & D_0 \notin \mathcal A_{t_0}. \end{cases} \]
Strictly, the LP needs a variable fixed to zero in the second case, since it only defines variables for \(D\in\mathcal A_t\). With that repair, the one-type, unit-mass instance is exactly the paper’s membership question with a scale factor. Other types do not affect the target, and the mass records how many copies of an already-solved instance there are. That makes this construction a batch of independent diagnosis questions, rather than a population-level question whose formulation depends on the society being continuous.
A more substantive version might allocate repairs across many hospital cases subject to a shared limit—for example, a cap on cases receiving repairs that suppress billing—and maximize the mass receiving an approved treatment. But that requires a common impact measure \(q_t(D)\) and a fleet-wide constraint such as \(\sum_{t,D}q_t(D)x_{t,D}\le B\). The paper supplies neither: its preferences compare diagnoses within an MCS, whose bridge rules are named and system-specific. In one integrated hospital MCS, a diagnosis modifies those shared rules; it does not assign a separate repair to each patient. In a fleet of separate MCSs, the new shared constraint is an additional cross-system policy. Either construction changes what the model is deciding.
That distinction is the negative case’s limit. A standardized fleet with a shared safety or capacity measure is plausible, and the authors might recognize constrained repair selection across such a fleet as a useful extension. So the proposed allocation does not establish a worthwhile mirror by itself, but I cannot rule out that stronger scenario. The honest case against is that Theorem 8’s direct lift is population-neutral, while a genuinely population-level version needs substantive structure beyond the paper’s diagnosis-selection model.
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.