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}\).
Theorem 2 — class: other
PDF text-layer excerpt — equations and symbol order may be approximateLet M be an MCS and let ⪯be a preference order on diagnoses of M. Then (D1, D2) ∈D± m,⪯(M) holds iff t(D1, D2) ∈D± m,tmax (M ⪯, brP , brH) holds.
statement extracted from the paper’s text layer; consult the paper for the exact wording
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 society is given by its support: a list \(T\) of \(\tau\) types with positive binary-rational masses \(\mu_t\), normalized by \(\sum_t\mu_t=1\). The parameter \(\tau\) counts listed types, not possible types. Each type specifies a finite propositional multi-context system \(M_t\) and a preference preorder \(\preceq_t\).
Each context \(i\) has a finite belief vocabulary and a Boolean circuit \(A_i(H,S_i)\) testing whether belief set \(S_i\) is acceptable when its fixed knowledge base receives the set \(H\) of bridge-rule heads. A bridge rule \((i:s)\leftarrow(j_1:p_1),\ldots,\operatorname{not}(j_k:p_k)\) fires exactly when its positive body beliefs are present and its negative body beliefs absent. An equilibrium is a tuple \(S\) satisfying \(A_i(H_i(S),S_i)=1\) for every context, where \(H_i(S)\) contains exactly the heads of firing rules into \(i\).
Write \(B_t\) for the bridge rules. A candidate diagnosis is \(D=(D_1,D_2)\in 2^{B_t}\times2^{B_t}\); it is a diagnosis if deleting \(D_1\) and adding unconditional copies of \(D_2\) yields an equilibrium. Overlap between \(D_1\) and \(D_2\) is allowed.
The reflexive, transitive relation \(\preceq_t\) is supplied by a Boolean comparison circuit, with \(D'\prec_t D\) meaning \(D'\preceq_t D\) and \(D\not\preceq_t D'\). A diagnosis is preferred if no diagnosis is strictly preferred to it. Define \(\mathcal R_t=D^{\pm}_{m,\preceq_t}(M_t)\) as the componentwise subset-minimal members of the preferred diagnoses; minimality is taken after preference selection.
Compute each \(\mathcal R_t\) explicitly and describe the full feasible set of real assignments \(x_{t,D}\geq0\) satisfying \(\sum_{D\in\mathcal R_t}x_{t,D}=\mu_t\), using a finite system of linear constraints. Let \(m=\max_t|B_t|\), \(L\) be the total input bit length, and \(B\) the output bit length.
Is this enumeration and polyhedral characterization computable in time polynomial in \(m,\tau,L,B\), or is it \(\mathrm{NP}\)-hard under polynomial-time Turing reductions?
For individual systems, a sound and complete clone construction realizes precisely the minimal preferred diagnoses. Recognizing a specified minimal preferred diagnosis is \(\Pi^P_2\)-hard even with polynomial-time context reasoning and preference comparison. [Verified results](https://acris.aalto.fi/ws/portalfiles/portal/27483329/11088_Article_Text_20618_1_10_20180216.pdf)
No result settling this exact mass-based enumeration problem was located in the search.
The problem is \(\mathrm{NP}\)-hard under polynomial-time Turing reductions, already when \(\tau=m=1\), the preference relation makes all candidates equivalent, and the output contains exactly one diagnosis.
Under the usual explicit-output convention, this rules out an algorithm polynomial in \(m,\tau,L,B\) unless \(\mathrm{P}=\mathrm{NP}\). Here the output consists of the diagnosis lists and their direct linear description; allowing arbitrary padding with redundant constraints would make the output-sensitive requirement vacuous.
The proof below does not rely on the supplied recognition-hardness result.
For each type \(t\), let \(Q_t\) denote the set of diagnoses. This set is computable by exhaustive search:
These searches are finite because the bridge-rule sets and belief vocabularies are finite.
Next compute the preferred diagnoses as
\(P_t=\{D\in Q_t:\text{ there is no }E\in Q_t\text{ with }E\preceq_t D\text{ and }D\not\preceq_t E\}\).
For pairs of rule sets, define \(E\subsetneq_{\mathrm{cw}}D\) to mean
\(E_1\subseteq D_1\), \(E_2\subseteq D_2\), and \(E\ne D\).
Then the required output is exactly
\(\mathcal R_t=\{D\in P_t:\text{ there is no }E\in P_t\text{ with }E\subsetneq_{\mathrm{cw}}D\}\).
This performs subset-minimality after preference selection, as required.
Once these lists are available, the complete feasible set is described by the finite rational linear system
\(x_{t,D}\geq 0\quad\text{for every }t\in T\text{ and }D\in\mathcal R_t,\)
\(\displaystyle\sum_{D\in\mathcal R_t}x_{t,D}=\mu_t\quad\text{for every }t\in T.\)
Necessity and sufficiency follow directly from the definition of a feasible assignment: there are no additional coupling conditions between types. If some \(\mathcal R_t\) is empty, its equation becomes \(0=\mu_t\), so the feasible set is empty because \(\mu_t>0\). Otherwise, each type contributes a simplex of nonnegative assignments with total mass \(\mu_t\).
This gives an exact finite algorithm. It does not establish an output-polynomial running time.
Let \(\varphi(z_1,\ldots,z_n)\) be an instance of propositional satisfiability. Construct a society with one type of mass \(1\).
Its system has one context, with belief vocabulary
\(\{h,z_1,\ldots,z_n\}\), and one unconditional bridge rule
\(r:(1:h)\leftarrow\).
Thus \(B_1=\{r\}\) and \(m=\tau=1\).
For a belief set \(S\), define the assignment \(a_S\) by
\(a_S(z_j)=1\) exactly when \(z_j\in S\).
Define the acceptance circuit by
\(A(H,S)=\neg\mathbf 1_{\{h\in H\}}\;\lor\;\varphi(a_S).\)
Consequently:
This is a valid Boolean acceptance circuit of size polynomial in the size of \(\varphi\). The circuit need not inspect whether \(h\in S\); the problem imposes no such requirement.
Finally, define the comparison circuit to return \(1\) for every pair of candidate diagnoses. Thus \(D'\preceq_1 D\) always holds. This relation is reflexive and transitive, and its strict part is empty. Every diagnosis is therefore preferred.
There are exactly four candidate diagnoses:
| Candidate | Heads received | Is a diagnosis exactly when |
|---|---|---|
| \((\varnothing,\varnothing)\) | \(\{h\}\) | \(\varphi\) is satisfiable |
| \((\{r\},\varnothing)\) | \(\varnothing\) | Always |
| \((\varnothing,\{r\})\) | \(\{h\}\) | \(\varphi\) is satisfiable |
| \((\{r\},\{r\})\) | \(\{h\}\) | \(\varphi\) is satisfiable |
To justify the head column, the original unconditional rule remains present unless it is deleted, while membership in \(D_2\) adds an unconditional copy. Hence the head \(h\) is absent exactly when \(r\in D_1\) and \(r\notin D_2\). Duplicate copies produce the same head set.
When \(H=\{h\}\), an equilibrium exists exactly when some assignment satisfies \(\varphi\), by the definition of \(A\). When \(H=\varnothing\), the belief set \(S=\varnothing\) supplies an equilibrium regardless of \(\varphi\). This proves every entry of the table.
If \(\varphi\) is satisfiable, all four candidates are diagnoses and all are preferred. The pair \((\varnothing,\varnothing)\) is componentwise contained in every other pair, strictly so for every distinct pair. Therefore
\(\mathcal R_1=\{(\varnothing,\varnothing)\}.\)
If \(\varphi\) is unsatisfiable, the only diagnosis is \((\{r\},\varnothing)\). It is preferred and componentwise subset-minimal among the preferred diagnoses. Therefore
\(\mathcal R_1=\{(\{r\},\varnothing)\}.\)
In particular, both cases have exactly one required diagnosis, and both have a nonempty feasible assignment set.
The reduction constructs an input of length polynomial in the size of \(\varphi\). A single call to the enumeration problem decides satisfiability: inspect whether its unique listed diagnosis is \((\varnothing,\varnothing)\) or \((\{r\},\varnothing)\).
Since propositional satisfiability is \(\mathrm{NP}\)-complete, this proves \(\mathrm{NP}\)-hardness under polynomial-time Turing reductions.
The output-size issue is also controlled. Using incidence vectors for diagnoses, the unique diagnosis has two bits. Its entire direct linear description is either
\(x_{1,(\varnothing,\varnothing)}\geq0,\qquad x_{1,(\varnothing,\varnothing)}=1,\)
or
\(x_{1,(\{r\},\varnothing)}\geq0,\qquad x_{1,(\{r\},\varnothing)}=1.\)
Thus \(B\) is bounded by a constant in the standard encoding. An algorithm polynomial in \(m,\tau,L,B\) would consequently decide satisfiability in polynomial time.
The explicit diagnosis labels carry the hardness: although both feasible sets are singletons, determining which diagnosis indexes that singleton decides satisfiability.
⟨structured verdict parsed — rendered above⟩
The prover’s output resolves the task correctly: it establishes \(\mathrm{NP}\)-hardness under polynomial-time Turing reductions, with bounded output size on the reduction instances. I found no major or minor mathematical issues.
The exhaustive-search procedure correctly computes the diagnoses.
The definition of \(P_t\) correctly excludes a diagnosis \(D\) precisely when another diagnosis \(E\) satisfies \(E\preceq_t D\) and \(D\not\preceq_t E\). This matches the specified strict preference relation.
The subsequent definition of \(\mathcal R_t\) tests componentwise subset-minimality within \(P_t\). Thus the order of preference selection and minimality is correct. No assumption that the preference preorder is total is used.
This establishes computability by a finite algorithm, without claiming that exhaustive search is polynomial.
The displayed nonnegativity constraints and one mass equation per type exactly reproduce the requested feasible-set definition. There are no omitted cross-type constraints in the task.
The empty-output case is handled correctly: if \(\mathcal R_t=\varnothing\), the corresponding equation is \(0=\mu_t\), which is inconsistent because the input requires \(\mu_t>0\).
When every \(\mathcal R_t\) is nonempty, the claimed product of simplices follows directly from the separate nonnegativity and mass constraints. All coefficients and right-hand sides have finite rational encodings.
The construction satisfies the input restrictions:
The acceptance circuit’s failure to inspect whether \(h\in S\) is legitimate. The task imposes no condition requiring supplied heads to belong to accepted belief sets.
The supplied recognition-hardness and clone-construction results are not used, so no unverified application of those results occurs.
The head \(h\) is absent exactly when the original rule is deleted and no unconditional copy is added. Therefore the table’s head sets are correct, including the overlapping candidate \((\{r\},\{r\})\).
For head set \(\{h\}\), acceptance reduces to satisfaction of \(\varphi\) by the assignment encoded in \(S\). Every assignment to the formula variables is representable by such a belief set, so equilibrium existence is equivalent to satisfiability.
For the empty head set, the acceptance circuit returns \(1\) for every belief set. The stated witness \(S=\varnothing\) is therefore valid.
Consequently, all four diagnosis classifications in the table are correct.
Because comparison holds in both directions for every pair, strict preference never holds. Every diagnosis is preferred.
If \(\varphi\) is satisfiable, all four candidates are diagnoses. The pair \((\varnothing,\varnothing)\) is a strict componentwise subset of each other candidate, so it is the unique required minimal preferred diagnosis.
If \(\varphi\) is unsatisfiable, the table leaves exactly one diagnosis, \((\{r\},\varnothing)\). It is necessarily preferred and subset-minimal.
Thus both branches have exactly one output diagnosis. Neither branch relies on an empty feasible set or another degenerate interpretation.
The construction is polynomial in the formula’s encoded length. Inspecting the unique enumerated diagnosis distinguishes satisfiable from unsatisfiable formulas with one oracle call.
The invoked theorem—that propositional satisfiability is \(\mathrm{NP}\)-complete—applies to the arbitrary propositional formula used as the reduction input. This establishes the claimed polynomial-time Turing hardness.
The bounded-output argument is also correct under the stated direct explicit-output convention. Each diagnosis has two incidence bits, and the linear description contains one nonnegativity constraint and one equality with right-hand side \(1\). Neither output requires reproducing the formula or the belief vocabulary.
Accordingly, a running-time bound polynomial in \(m,\tau,L,B\) would be polynomial in the formula length on these instances and would decide satisfiability in polynomial time.
The prover appropriately identifies the output-encoding convention and the redundant-padding concern. This is a clarification of the intended output-sensitive interpretation, not a missing mathematical step. The conclusion is correctly conditional: an output-polynomial algorithm is ruled out unless \(\mathrm{P}=\mathrm{NP}\).
No additional clarification or repair is needed.
⟨structured verdict parsed — rendered above⟩
Tier: machine-proved, adversarially reviewed by an independent model. No human has checked this proof. Generated from pipeline artifacts by tools/atlas_build.py.