| paper | d4-conf-ijcai-2018-0466 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
other→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{NP}\)-hard under polynomial-time Turing reductions, already for \(m=\tau=1\) with exactly one output diagnosis; output-polynomial computation would imply \(\mathrm{P}=\mathrm{NP}\). · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 2
statement extracted from the paper’s text layer
Given a finite set of complete encounter MCS types \(T\), binary-rational masses \(\mu_t\), and preference orders \(\preceq_t\), compute \(\mathcal R_t=D^\pm_{m,\preceq_t}(M_t)\) for each type and characterize all mass assignments \(x_{t,D}\ge 0\) with \(\sum_{D\in\mathcal R_t}x_{t,D}=\mu_t\).
A distribution over complete, recurring encounter MCS specifications, where each type includes its contexts, knowledge bases, bridge rules, and preference order. Each unit of mass receives one integral preferred diagnosis; \(x_{t,D}\) records the cohort mass of type \(t\) receiving diagnosis \(D\).
Each encounter has its own MCS, so no shared constraint makes the mass assignment consequential; it can be any mixture of diagnoses already computed for each type.
fatal: False
The mirror covers Theorem 2’s correspondence when applied to each MCS type and the resulting cohort of minimal preferred diagnoses. It leaves aside joint repairs to a shared MCS, cross-encounter constraints, and aggregate preferences.
The strongest positive case is a narrow population-scale diagnosis-selection problem: many repeated system cases, each repaired according to the paper’s preferred-diagnosis semantics.
The strongest numbered anchor in the supplied text is Theorem 2, proved in this paper. It says that, for an MCS \(M\) and a preference order \(\preceq\), a diagnosis \(D\) is minimal \(\preceq\)-preferred in \(M\) if and only if its corresponding diagnosis \(t(D)\) is a subset-minimal prioritized-minimal diagnosis containing \(t_{\max}\) in the cloned, meta-reasoning system \(M^\preceq\). This is a correctness result for an encoding the paper computes with. Separately, §6 and Table 1 report complexity results for diagnosis membership and say the underlying minimal-preferred-diagnosis problem is hard for the same class as the basic diagnosis problem. The supplied text has no numbered theorem asserting a complexity class, so it does not provide a numbered hardness anchor in the strictest sense.
Here is the mirror I would put to a prover. Call it Mass-Distributed Minimal-Preferred Diagnosis. An instance consists of a finite set \(T\) of types, positive binary-rational masses \(\mu_t\) summing to \(1\), and, for each \(t\), a complete MCS specification \(M_t\) and preference order \(\preceq_t\). A type includes everything the diagnosis problem uses: contexts and their logics and knowledge bases, bridge rules, protected and prioritized rules, and the preference order. Let
\[
\mathcal R_t = D^\pm_{m,\preceq_t}(M_t).
\]
The task is to compute each \(\mathcal R_t\) and a feasible diagnosis-mass assignment \(x\) satisfying
\[
x_{t,D}\ge 0,\qquad
\sum_{D\in\mathcal R_t}x_{t,D}=\mu_t\quad\text{for every }t.
\]
Thus \(x_{t,D}\) is the fraction of the population of type \(t\) assigned diagnosis \(D\). A solution lists the minimal preferred diagnoses and assigns all mass for each type among them. The paper deliberately permits user-chosen preference formalisms, so there is no faithful common scalar objective to add; the natural output is the set of admissible repairs and their mass distribution. A decision version, useful for evaluating a proposed repair policy, asks whether the types whose designated diagnosis belongs to \(\mathcal R_t\) have total mass at least a given rational threshold.
A plausible regime is a large service system handling many recurring cases—such as standardized hospital encounters—with a small catalog of complete case and system templates. The unit is an encounter; its type fixes the full information and preference specification relevant to diagnosis. The mass is the share of encounters of that type. Millions of encounters over a modest number \(\tau=|T|\) of templates are plausible, though the type definition must include all relevant inputs and preferences; merely sharing a clinical label would not suffice.
I expect hardness to transfer for this mirror. At \(\tau=1\) and mass \(1\), diagnosis membership is exactly the original problem; aggregating over types cannot make the per-type reasoning disappear. For several independent types, the population task amounts to solving the diagnosis problem type by type and aggregating the results. The complexity claims in §6 support this expectation, but the exact complexity anchor is the table-level result, not Theorem 2.
The weakest point is the population interpretation. The paper diagnoses one coupled MCS; this mirror diagnoses many case-specific MCS instances. Repeated, standardized cases make that a credible high-multiplicity regime, but authors might regard it as batch diagnosis rather than a continuous form of their central problem. Also, the mass distribution itself adds little algorithmic structure when cases are independent. The positive case rests on the practical value of identifying preferred repairs across a large cohort, not on a claim that continuity makes the underlying diagnosis computation tractable.
Theorem 2 is the proponent’s strongest numbered anchor, but it establishes a representation equivalence: a diagnosis is minimal \(\preceq\)-preferred exactly when its encoded diagnosis has the corresponding minimality properties in the cloned MCS. It says nothing about population-scale computation. The clones are a way to compare two diagnoses of one system, not repeated units of a society. Lift the equivalence pointwise to types \(t\) with masses \(\mu_t\), and the mass plays no role in the result. The complexity claims in §6 are more promising anchors, though they appear in a table rather than as numbered complexity theorems.
The proposed encounter cohort is plausible, so the objection cannot be that repeated cases are impossible. But a type must include the complete MCS relevant to diagnosis: its contexts, knowledge bases, bridge rules, and preference specification. With a small catalog of such types, the proposed sets \(\mathcal R_t\) are just separate diagnosis problems. The assignment \(x\) can put all of each type’s mass on any one diagnosis in \(\mathcal R_t\); there is no shared constraint or objective that makes splitting the mass meaningful. The threshold query is a prevalence-weighted sum of per-type membership answers. That is a valid batch-analysis question, but its population is an outer wrapper around the paper’s computational problem.
A shared hospital MCS offers a stronger population story, yet its diagnoses alter bridge rules for the system. The patient example makes this explicit: removing a rule changes information flow in the MCS, not the treatment of a chosen fraction of patients. To assign different diagnoses to different encounters, one must create separate MCS instances. That restores the batch setting. To make those instances interact through a shared repair budget, shared rules, or a population-level preference, one must define new semantics and a new computational problem; the paper supplies no common cost or preference scale for aggregating its arbitrary, system-specific preference orders.
Treating contexts themselves as the population has a similar difficulty. Bridge rules refer to named contexts, and the contexts can have different logics, knowledge bases, roles, and connections. A type description that preserves those connections may distinguish nearly every context; collapsing them into masses loses network structure. A continuum model that preserves the structure would be a substantial extension of MCS diagnosis, rather than a direct mirror of the paper’s results.
So the negative case is strongest against the specific anchors: Theorem 2 lifts pointwise, and the §6 complexity problems remain single-MCS queries with no population-level choice to compute. It is weaker as a universal claim. Repeated standardized encounters are credible, and a new population model for interacting systems might be worthwhile. What I cannot make persuasive is that either proposal is a continuous mirror of the computational results this paper actually establishes.
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.