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.
Theorem 8 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateIf CC(M) is hard for ΣP i (ΠP i ) then MCSDMPREF is hard for ΠP i+1 (ΠP i+2) with i ≥0. Moreover, MCSDMPREF is ΠP 2 -hard even if both CC(M) and deciding D′ ⪯D′′ are in P. For establishing completeness of MCSDMPREF, we use the clone encoding of the previous section as a polynomial-time reduction to MCSDPHm,tmax .
statement extracted from the paper’s text layer; consult the paper for the exact wording
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 given by its support: a list \(T\) of \(\tau\) types with positive binary rational masses \(\mu_t\), summing to \(1\); \(\tau\) counts supplied types, not possible types.
Each type supplies a finite multi-context system \(M_t\) and a preference circuit. Context \(i\) has a knowledge base \(kb_i\), bridge rules, and an acceptability function \(\operatorname{ACC}_i\). Its supplied Boolean circuit \(A_i(H,U)\) decides whether some \(S_i\in\operatorname{ACC}_i(kb_i\cup H)\) satisfies \(S_i\cap O_i=U\), where \(O_i\) lists the beliefs of context \(i\) mentioned in bridge-rule bodies; \(H\) is a subset of its possible bridge heads. Each context is consistent without bridge input.
A bridge rule \((i:s)\leftarrow(j_1:p_1),\ldots,(j_a:p_a),\operatorname{not}(k_1:q_1),\ldots,\operatorname{not}(k_b:q_b)\) adds \(s\) exactly when all positive beliefs occur and all negative beliefs are absent. An equilibrium consists of sets \(U_i\subseteq O_i\) with \(A_i(H_i,U_i)=1\) for every context, where \(H_i\) contains exactly the heads of its applicable rules. Each supplied \(M_t\) has no equilibrium.
Write \(B_t\) for its bridge rules. A candidate diagnosis is \(D=(D_1,D_2)\in 2^{B_t}\times2^{B_t}\), allowing overlap; it is a diagnosis if replacing the rules by \((B_t\setminus D_1)\cup\operatorname{cf}(D_2)\) admits an equilibrium, where \(\operatorname{cf}\) deletes rule bodies.
The preference circuit represents a promised reflexive, transitive relation \(\preceq_t\) on all candidate diagnoses, with \(D\prec_t E\) meaning \(D\preceq_t E\) and \(E\not\preceq_t D\). Let \(P_t\) contain the diagnoses with no strictly preferred diagnosis, and let \(\mathcal A_t\) contain those elements of \(P_t\) having no proper componentwise subset in \(P_t\). Thus preference selection precedes subset minimization; totality is not required.
Given \(t_0\in T\) and a candidate diagnosis \(D_0\) for \(M_{t_0}\), maximize \(x_{t_0,D_0}\) over real masses \(x_{t,D}\geq0\), indexed implicitly by \(D\in\mathcal A_t\), subject to \(\sum_{D\in\mathcal A_t}x_{t,D}=\mu_t\). Interpret the objective as \(0\) when \(D_0\notin\mathcal A_{t_0}\), and report infeasibility if any \(\mathcal A_t\) is empty.
Let \(m=\max_t|B_t|\), \(n\) be the maximum number of contexts per type, and \(L\) the total input bit length, including circuits, rules, masses, and target.
Is computing the exact optimum, including detecting infeasibility, polynomial-time in \(m,\tau,n,L\), or is deciding whether a feasible allocation has objective at least a supplied binary rational \(q\in[0,1]\) NP-hard?
Discrete diagnosis recognition is \(\Pi_2^P\)-hard even with polynomial-time projected context acceptability and preference comparison. [Eiter and Weinzierl (2017)](https://doi.org/10.1613/jair.5416)
No result settling this distribution-based allocation problem was located in the literature search.
The threshold decision problem is \(\mathrm{NP}\)-hard, even when \(\tau=n=1\), \(\mu_{t_0}=q=1\), and the preference relation is universal indifference.
Consequently, computing the exact optimum in polynomial time in \(m,\tau,n,L\) would imply \(\mathrm{P}=\mathrm{NP}\). Under the stated promises, allocation infeasibility never occurs.
Fix a supplied type \(t\). The candidate diagnosis \((B_t,\varnothing)\) deletes every bridge rule. Each context then receives empty bridge input. By the promise of consistency without bridge input, choose an acceptable belief set for each context and project it onto \(O_i\). These projections form an equilibrium. Thus every type has at least one diagnosis.
The candidate set is finite. Since \(\preceq_t\) is reflexive and transitive, its strict part is irreflexive and transitive. Consequently, every nonempty finite set of diagnoses has an element with no strictly preferred diagnosis: otherwise repeatedly choosing a strictly preferred diagnosis would eventually produce a cycle, contradicting these properties. Hence \(P_t\ne\varnothing\).
Choose an element of \(P_t\) minimizing \(|D_1|+|D_2|\). Every proper componentwise subset has smaller cardinality, so this element belongs to \(\mathcal A_t\). Therefore \(\mathcal A_t\ne\varnothing\) for every supplied type.
An allocation exists: for each type, assign all of its mass to any one element of \(\mathcal A_t\).
If \(D_0\in\mathcal A_{t_0}\), nonnegativity and the mass constraint give \(x_{t_0,D_0}\le\mu_{t_0}\). Equality is attainable by assigning all mass of type \(t_0\) to \(D_0\). Otherwise, the objective is \(0\) by definition. Thus
\(\displaystyle \operatorname{OPT}= \begin{cases} \mu_{t_0},&D_0\in\mathcal A_{t_0},\\ 0,&D_0\notin\mathcal A_{t_0}. \end{cases}\)
In particular, for \(0<q\le\mu_{t_0}\), the threshold answer is yes exactly when \(D_0\in\mathcal A_{t_0}\). For \(q=0\), it is always yes; for \(q>\mu_{t_0}\), it is always no.
Let \(\varphi(z_1,\ldots,z_k)\) be a Boolean formula whose satisfiability is to be decided. Construct a society with one type, mass \(1\), and one context.
Use distinct beliefs \(p,z_1,\ldots,z_k,a,b,c\). Set the knowledge base to \(\varnothing\), and supply these bridge rules:
\(\displaystyle r:\ (1:a)\leftarrow\operatorname{not}(1:p),\)
\(\displaystyle g:\ (1:b)\leftarrow,\)
\(\displaystyle v_j:\ (1:c)\leftarrow(1:z_j)\qquad(1\le j\le k).\)
Thus the observed beliefs are exactly \(O=\{p,z_1,\ldots,z_k\}\), and the possible bridge heads are \(\{a,b,c\}\).
For \(U\subseteq O\), let \(\varphi(U)\) denote the value of \(\varphi\) under the assignment making \(z_j\) true exactly when \(z_j\in U\). Define the projected acceptability circuit by
\(\displaystyle A(H,U)= \bigl((p\in U)\leftrightarrow(a\in H)\bigr) \land \bigl((b\notin H)\lor\varphi(U)\bigr). \)
The head \(c\) does not affect acceptability.
To verify that this circuit represents a valid finite context, define, for each knowledge base \(K\subseteq\{a,b,c\}\),
\(\displaystyle \operatorname{ACC}(K)= \left\{ K\cup U: U\subseteq O,\ \bigl((p\in U)\leftrightarrow(a\in K)\bigr) \land \bigl((b\notin K)\lor\varphi(U)\bigr) \right\}. \)
The head vocabulary is disjoint from \(O\), so every listed belief set projects to precisely \(U\). Therefore the supplied circuit has exactly the required projected-acceptability semantics.
With no bridge input, \(K=\varnothing\), and \(U=\varnothing\) is acceptable: both sides of the equivalence are false, and \(b\notin K\). The context is therefore consistent without bridge input, independently of whether \(\varphi\) is satisfiable.
Finally, let the preference circuit return true on every pair of candidate diagnoses. This relation is reflexive and transitive, and its strict part is empty. Set
\(\displaystyle D_0=(\{r\},\varnothing),\qquad \mu_{t_0}=q=1.\)
The construction has \(m=k+2\) bridge rules and polynomial input length. Its acceptability circuit contains one copy of \(\varphi\), and its preference circuit is constant.
Suppose \(U\) were an equilibrium, with applicable-head set \(H\).
The only rule with head \(a\) is \(r\), whose body holds exactly when \(p\notin U\). Therefore
\(\displaystyle a\in H\ \Longleftrightarrow\ p\notin U.\)
Acceptability requires
\(\displaystyle p\in U\ \Longleftrightarrow\ a\in H.\)
Together these would imply \(p\in U\) exactly when \(p\notin U\), a contradiction. Thus the constructed system satisfies the promised absence of an equilibrium.
Applying \(D_0\) deletes \(r\) and forces no rules. Consequently, \(a\notin H\), while the unconditional rule \(g\) guarantees \(b\in H\). Acceptability therefore requires precisely \(p\notin U\) and \(\varphi(U)=1\).
If an equilibrium exists, its assignment to the \(z_j\) satisfies \(\varphi\).
Conversely, suppose an assignment satisfies \(\varphi\). Choose \(U\) to contain its true variables and to omit \(p\). The applicable-head set is \(\{b,c\}\) if at least one variable is true, and \(\{b\}\) otherwise. In either case, \(a\notin H\), \(b\in H\), and \(A(H,U)=1\). Hence this \(U\) is an equilibrium.
Thus
\(\displaystyle D_0\text{ is a diagnosis}\ \Longleftrightarrow\ \varphi\text{ is satisfiable}.\)
Because the strict preference relation is empty, \(P_{t_0}\) consists of all diagnoses.
The only proper componentwise subset of \(D_0=(\{r\},\varnothing)\) is \((\varnothing,\varnothing)\). This candidate leaves the original system unchanged, so it is not a diagnosis.
Therefore, whenever \(D_0\) is a diagnosis, it also belongs to \(\mathcal A_{t_0}\). Conversely, membership in \(\mathcal A_{t_0}\) entails being a diagnosis. Consequently,
\(\displaystyle D_0\in\mathcal A_{t_0}\ \Longleftrightarrow\ \varphi\text{ is satisfiable}.\)
By Section 1, every constructed allocation instance is feasible. Since \(\mu_{t_0}=q=1\),
\(\displaystyle \varphi\text{ is satisfiable} \ \Longleftrightarrow\ \operatorname{OPT}=1 \ \Longleftrightarrow\ \text{some feasible allocation has objective at least }q. \)
This is a polynomial-time many-one reduction from Boolean satisfiability, proving the requested \(\mathrm{NP}\)-hardness. It directly verifies all promises of the supplied circuit model and does not require transferring a diagnosis-recognition theorem from another representation.
⟨structured verdict parsed — rendered above⟩
The argument establishes the requested NP-hardness. Its feasibility argument and reduction are sound. There is one minor boundary-case inaccuracy in the description of the head vocabulary; it does not affect the reduction or its conclusion.
The candidate \((B_t,\varnothing)\) removes every bridge rule, so every context receives empty bridge input. The consistency promise supplies an acceptable belief set for each context. Projecting these sets onto their respective \(O_i\) gives an equilibrium under the specified circuit semantics. Thus every supplied type has a diagnosis.
The argument establishing \(P_t\ne\varnothing\) is valid. Restricting the promised preorder to the finite, nonempty set of diagnoses preserves reflexivity and transitivity. Its strict part is irreflexive and transitive, so repeatedly choosing a strictly preferred diagnosis cannot continue indefinitely in that finite set.
Minimizing \(|D_1|+|D_2|\) over \(P_t\) correctly produces an element of \(\mathcal A_t\): every proper componentwise subset has strictly smaller total cardinality. Allowing overlap between the two components does not change this fact.
Consequently, every \(\mathcal A_t\) is nonempty, and assigning each type’s entire mass to one selected element satisfies all allocation constraints. The conclusion that infeasibility never occurs follows from the stated promises.
If \(D_0\in\mathcal A_{t_0}\), its mass cannot exceed \(\mu_{t_0}\), because all masses are nonnegative and their sum for that type is \(\mu_{t_0}\). Concentrating that type’s mass on \(D_0\) attains the bound. The choices for other types are independent.
If \(D_0\notin\mathcal A_{t_0}\), the task explicitly defines the objective to be zero. Thus the stated two-case optimum is correct.
The threshold conclusions also cover all permitted boundary cases: feasibility makes the answer yes for \(q=0\); membership determines the answer for \(0<q\le\mu_{t_0}\); and the answer is no for \(q>\mu_{t_0}\).
The observed vocabulary is correctly identified: \(p\) occurs in the body of \(r\), and each \(z_j\) occurs in the body of \(v_j\). The head vocabulary is disjoint from these observations.
For every admissible bridge input \(H\), the supplied definition of \(\operatorname{ACC}(H)\) has exactly the projections accepted by \(A(H,U)\). Therefore the circuit has the required semantics. The potentially exponential family of acceptable sets is described semantically; the supplied projected-acceptability circuit remains polynomial in the formula length.
Empty bridge input is consistent: \(U=\varnothing\) satisfies the equivalence, and the second conjunct is true independently of the formula. The constant-true preference circuit defines a reflexive, transitive relation with empty strict part.
The construction supplies one type and one context, valid rational mass and threshold equal to \(1\), and \(k+2\) rules. Its circuits and rule descriptions have polynomial length.
Minor issue: If \(k=0\) is allowed, no \(v_j\) exists, so \(c\) is not a possible bridge head. The sentence asserting that the possible bridge heads are exactly \(\{a,b,c\}\) then overstates that set. Since the circuit ignores \(c\), this does not invalidate the hardness argument. Minimum clarification: explicitly restrict the source instances to \(k\ge1\), or correct the head-vocabulary statement for \(k=0\).
The rule \(r\) is the sole source of \(a\), and it applies exactly when \(p\notin U\). Acceptability requires \(p\in U\) exactly when \(a\in H\). These requirements contradict each other for either truth value of \(p\). The original system therefore satisfies the promised absence of an equilibrium, independently of satisfiability.
Applying \(D_0\) removes the sole source of \(a\), retains the unconditional source of \(b\), and forces no rules. Hence acceptability requires exactly \(p\notin U\) and a satisfying assignment to the formula.
Both directions are verified. An equilibrium supplies a satisfying assignment. Conversely, a satisfying assignment determines \(U\); the stated applicable-head set correctly accounts for whether any \(v_j\) fires, and satisfies the circuit.
Universal indifference makes every diagnosis preference-selected. The only proper componentwise subset of \(D_0\) is \((\varnothing,\varnothing)\), which leaves the inconsistent original system unchanged. Therefore \(D_0\) is selected and subset-minimal exactly when it is a diagnosis.
The reduction maps satisfiable formulas precisely to feasible allocation instances attaining threshold \(1\). All constructed instances satisfy the promises, including those arising from unsatisfiable formulas. Together with the standard NP-hardness of Boolean satisfiability, this establishes polynomial-time many-one NP-hardness.
An exact polynomial-time optimizer would decide these threshold instances by distinguishing optimum \(0\) from optimum \(1\), implying \(\mathrm P=\mathrm{NP}\). The prover claims hardness, not membership in NP, and the argument supports that distinction.
⟨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.