Answer: Exact computation of the bound and its certified removals is \(\mathrm{NP}\)-hard. Deciding \(B(D)>q\), or whether a specified pair is removed, is \(\mathrm{NP}\)-complete.
Theorem 2 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateAlgorithm 3 finds a valid lower bound on the maximal Hamming distance to a set of ideals, filters the do- mains with respect to this bound and runs in O(nd2k).
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given current finite domains \(D_1,\ldots,D_n\), a radius \(q\), and a binary-rational society \(\mu\) supported on types \(T\), each with one ideal \(v^t\), compute the subset-average lower bound \(B(D)=\max_{\emptyset\ne S\subseteq T}\left\lceil\frac{1}{|S|}\sum_{i=1}^{n}\min_{a\in D_i}\sum_{t\in S}\mathbb{1}[a\ne v_i^t]\right\rceil\), and prune each \(a\in D_i\) whose corresponding bound with \(X_i=a\) fixed exceeds \(q\). The requested output is this sound bound and the values it certifies can be removed; retained values need not have supporting completions.
Let \(m\geq1\) be the number of coordinates. Each coordinate has a finite alphabet \(A_i\) and an explicitly listed nonempty current domain \(D_i\subseteq A_i\); ideals are complete vectors \(v^t\in\prod_{i=1}^{m}A_i\), possibly outside the current domains. The radius is an integer \(q\in\{0,\ldots,m\}\).
A society is given by its support: a list \(T\) of \(\tau\geq1\) types with positive binary-rational masses \(\mu_t\), summing to \(1\), each with one ideal. Here \(\tau\) is the support size, not the number of possible types. Let \(L\) be the total input bit length and \(d=\max_i|D_i|\); state running times in \(m,\tau,d,L\).
The distance constraint requires \(\max_{t\in T}\sum_{i=1}^{m}\mathbf{1}[x_i\ne v_i^t]\leq q\) for an assignment \(x\in\prod_iD_i\). Only this constraint and the current domains are considered.
Define \(B(D)=\max_{\emptyset\ne S\subseteq T}\left\lceil\frac{1}{|S|}\sum_{i=1}^{m}\min_{a\in D_i}\sum_{t\in S}\mathbf{1}[a\ne v_i^t]\right\rceil\). Subsets consist of whole support types, and their averages are unweighted, irrespective of their masses.
For \(a\in D_i\), let \(D^{i,a}\) replace \(D_i\) by \(\{a\}\). The requested output is \(B(D)\) and exactly the pairs \((i,a)\) with \(B(D^{i,a})>q\), evaluated on the input domains; retained values need not admit supporting completions.
Is exact computation of this bound and its certified removals polynomial-time solvable, or is it \(\mathrm{NP}\)-hard?
For finite sets of \(k\) ideals, subset enumeration gives a sound lower bound and filtering, with a claimed running time of \(O(md2^k)\), hence fixed-parameter tractability in \(k\). Exact generalized arc consistency for the maximum-Hamming-distance constraint is separately known to be \(\mathrm{NP}\)-hard. [Verified source](https://cgi.cse.unsw.edu.au/~tw/howijcai07.pdf)
No hardness classification for exact computation of this subset-average bound, or result settling the specified distribution-input problem, was located in the search.
Exact computation of the requested bound and removals is \(\mathrm{NP}\)-hard. More precisely:
Nevertheless, the complete requested output can be computed in \(O(md\,2^\tau)\) arithmetic operations after polynomial preprocessing. Thus it is fixed-parameter tractable in the support size \(\tau\).
For a nonempty subset \(S\subseteq T\), define
\( s=|S|,\qquad c_{i,a}(S)=|\{t\in S:v_i^t=a\}|,\qquad M_i(S)=\max_{a\in D_i}c_{i,a}(S). \)
The minimum number of disagreements at coordinate \(i\) is \(s-M_i(S)\). Consequently, writing
\( F_D(S)=ms-\sum_{i=1}^m M_i(S), \)
we have
\( B(D)=\max_{\emptyset\ne S\subseteq T} \left\lceil\frac{F_D(S)}{|S|}\right\rceil. \)
Because \(q\) is an integer,
\( B(D)>q \quad\Longleftrightarrow\quad \exists\,\emptyset\ne S\subseteq T:\ F_D(S)>q|S|. \)
A subset \(S\), represented by its \(\tau\) membership bits, is therefore a polynomial-size certificate. Its counts and the displayed inequality can be checked in polynomial time. Hence this decision problem belongs to \(\mathrm{NP}\).
Fixing coordinate \(i\) to \(a\) replaces \(M_i(S)\) by \(c_{i,a}(S)\), giving
\( F_{D^{i,a}}(S)=F_D(S)+M_i(S)-c_{i,a}(S). \)
Thus the specified-pair removal decision also belongs to \(\mathrm{NP}\).
These certificates are sound for the distance constraint: if an assignment \(x\) has distance at most \(q\) from every selected type, then
\( F_D(S)\leq \sum_{t\in S}\sum_i\mathbf 1[x_i\ne v_i^t] \leq q|S|. \)
The same argument applies to assignments fixing \(x_i=a\).
We use the known \(\mathrm{NP}\)-completeness of Exact Cover: given an explicitly listed finite universe \(U\) and subsets \(C_1,\ldots,C_n\subseteq U\), decide whether some subfamily covers every element exactly once. This is problem 14 in [Karp’s original paper](https://www.cs.umd.edu/~gasarch/BLOGPAPERS/Karp.pdf).
We may restrict to a nonempty universe and nonempty, distinct sets. Empty sets and duplicates can be deleted without changing the answer; empty-universe instances are trivial and can be mapped to a fixed positive instance. Thus these restrictions preserve hardness.
Write \(u=|U|\), with \(u,n\geq1\). Create the support
\( T=\{t_0,t_1,\ldots,t_n\},\qquad \tau=n+1. \)
Type \(t_0\) is an anchor, and type \(t_j\) represents \(C_j\). Every coordinate constructed below has alphabet \(\{0,1,2\}\) and domain \(\{0,1\}\).
First construct a block of coordinates.
The block contains
\( h=2u+\sum_{j=1}^n(u-|C_j|) \)
coordinates. All ideals are complete; the symbol \(2\) is permitted in an ideal even though it lies outside the current domain.
Fix a nonempty \(S\subseteq T\). Define
\( z=\mathbf 1[t_0\in S],\qquad y_j=\mathbf 1[t_j\in S],\qquad s=z+\sum_j y_j, \)
and, for each element,
\( c_e=\sum_{j:e\in C_j}y_j. \)
Define the nonnegative integer
\( E(S)=\sum_{e\in U}|c_e-z|. \)
At either coordinate belonging to element \(e\), the two domain-value matching counts are \(c_e\) and \(z\). The sum of the maximum matching counts over its two copies is
\( 2\max(c_e,z)=c_e+z+|c_e-z|. \)
Each padding coordinate for \(j\) has maximum matching count \(y_j\). Therefore the sum of maximum matching counts over the entire block is
\( \begin{aligned} \sum_{\text{block }i}M_i(S) &=\sum_{e\in U}(c_e+z+|c_e-z|) +\sum_j(u-|C_j|)y_j\\ &=\sum_j|C_j|y_j+uz+E(S) +\sum_j(u-|C_j|)y_j\\ &=us+E(S). \end{aligned} \)
The block’s minimum total disagreement is consequently
\( F_{\mathrm{block}}(S)=(h-u)s-E(S). \)
We claim that a nonempty subset \(S\) satisfies \(E(S)=0\) exactly when it consists of the anchor together with an exact cover.
If \(z=0\), then \(E(S)=0\) forces every \(c_e=0\). Since every \(C_j\) is nonempty, selecting any \(t_j\) would make some \(c_e\) positive. Thus no type would be selected, contradicting \(S\ne\emptyset\).
Hence \(E(S)=0\) requires \(z=1\). It then requires \(c_e=1\) for every element, which says precisely that the selected sets cover each element exactly once. Conversely, an exact cover together with the anchor gives \(E(S)=0\).
Repeat every coordinate of the block \(R=\tau=n+1\) times. The resulting instance has
\( m=Rh,\qquad K=R(h-u). \)
For every nonempty subset,
\( \frac{F_D(S)}{|S|} =K-\frac{R E(S)}{|S|}. \)
In particular, \(B(D)\leq K\).
If the Exact Cover instance is positive, Section 2 supplies a subset with \(E(S)=0\), so \(B(D)=K\).
If it is negative, every nonempty subset has \(E(S)\geq1\). Since \(|S|\leq\tau=R\),
\( \frac{R E(S)}{|S|}\geq1. \)
Every subset average is then at most \(K-1\), and its ceiling is also at most \(K-1\). Therefore
\( \text{Exact Cover is positive} \quad\Longleftrightarrow\quad B(D)>K-1. \)
Set the reduction’s radius to \(q=K-1\). This is admissible: \(h-u\geq u\geq1\), so \(K\geq1\), while \(m-K=Ru>0\). Hence \(0\leq q\leq m\).
Let \(P=2^{\lceil\log_2\tau\rceil}\). Assign
\( \mu_{t_0}=\frac{P-n}{P}, \qquad \mu_{t_j}=\frac1P\quad(1\leq j\leq n). \)
These masses are positive dyadic rationals, sum to \(1\), and require \(O(\tau\log\tau)\) bits altogether. Their values do not affect any subset calculation.
Moreover,
\( h\leq(n+2)u,\qquad m\leq(n+1)(n+2)u. \)
The explicitly listed ideal table has \(m\tau=O((n+1)^3u)\) constant-size entries. All remaining data also have polynomial encoding length. The reduction is therefore polynomial-time.
Together with Section 1, this proves that deciding \(B(D)>q\) is \(\mathrm{NP}\)-complete. An exact algorithm for \(B(D)\) would decide this problem, proving the requested computation \(\mathrm{NP}\)-hard.
Take the constructed instance and append one coordinate \(i_\star\), with domain \(\{0,1\}\) and ideal \(0\) for every type. Let the extended domains be \(D'\).
For every subset, this coordinate contributes zero minimum disagreement. Hence
\( B(D')=B(D). \)
If this coordinate is fixed to \(1\), it contributes \(|S|\) disagreements to every selected subset. Every subset average increases by exactly \(1\), so
\( B((D')^{i_\star,1})=B(D)+1. \)
Use radius \(q'=K\), which is valid for the extended instance. The initial bound always passes, since \(B(D')\leq K=q'\). Nevertheless,
\( \begin{aligned} B((D')^{i_\star,1})>q' &\quad\Longleftrightarrow\quad B(D)+1>K\\ &\quad\Longleftrightarrow\quad B(D)=K\\ &\quad\Longleftrightarrow\quad \text{Exact Cover is positive}. \end{aligned} \)
Thus deciding this one certified removal is \(\mathrm{NP}\)-hard even under the restriction \(B(D')\leq q'\). With its polynomial certificate from Section 1, the general specified-pair decision is \(\mathrm{NP}\)-complete.
The hardness result is compatible with enumeration over the support.
Preprocess each ideal entry to record which domain value it matches, if any. Enumerate subsets in Gray-code order, so consecutive subsets differ by one type. Maintain the subset size and all counts \(c_{i,a}(S)\).
For each nonempty subset:
\( F_D(S)+M_i(S)-c_{i,a}(S)>q|S|. \)
Changing one selected type updates at most one count per coordinate. Scanning the counts and testing every pair costs \(O(md)\) arithmetic operations per subset. Thus the complete output takes
\( O(md\,2^\tau) \)
arithmetic operations after preprocessing. Every test uses the original input domains, so this produces exactly the requested pairs without iterative propagation.
For an explicit bit-time bound, straightforward domain-label comparisons take \(O((d+\tau)L)\) preprocessing time: each ideal label is compared with at most \(d\) domain labels, and each domain label with at most \(\tau\) ideal labels. All subsequent integers have \(O(\log(m\tau+2))\) bits. Using schoolbook integer arithmetic gives the conservative bound
\( O\!\left((d+\tau)L+ md\,2^\tau\log^2(m\tau+2)\right), \)
with polynomial space.
The exponential parameter is the listed support size \(\tau\). The binary masses do not require expansion into individual agents.
⟨structured verdict parsed — rendered above⟩
The output establishes the requested hardness classification, with one minor omission concerning preprocessing of trivial Exact Cover instances. The counting identity, reduction, ceiling separation, removal construction, and enumeration bounds are sound. No major issue was found.
For every nonempty \(S\subseteq T\), putting \(s=|S|\), choosing \(a\in D_i\) produces exactly \(s-c_{i,a}(S)\) disagreements at coordinate \(i\). Since the domains are nonempty and coordinates are minimized independently, the stated identity
\(F_D(S)=ms-\sum_i M_i(S)\)
is correct.
The equivalence
\(B(D)>q\iff\exists S\ne\emptyset:F_D(S)>q|S|\)
correctly uses the integrality of \(q\). It handles equality correctly: a subset average equal to \(q\) does not certify removal.
A subset encoded by its \(\tau\) membership bits is a polynomial-size certificate. All counts, maxima, and integer comparisons can be computed in polynomial time in the explicitly listed input. Thus both claimed decision problems belong to \(\mathrm{NP}\).
Replacing \(D_i\) by \(\{a\}\) replaces its maximum matching count by \(c_{i,a}(S)\), so
\(F_{D^{i,a}}(S)=F_D(S)+M_i(S)-c_{i,a}(S)\)
follows exactly.
For any assignment in the relevant domains, its aggregate disagreement over \(S\) is at least the coordinatewise minimum \(F_D(S)\). If every selected type has distance at most \(q\), that aggregate is at most \(q|S|\). Therefore the certificates are sound.
The argument establishes precisely the requested bound-based filtering. It does not assert that retained values have supporting completions.
The invoked theorem is the \(\mathrm{NP}\)-completeness of explicitly represented Exact Cover: deciding whether a subfamily covers each universe element exactly once. This matches problem 14 in [Karp’s paper](https://www.cs.umd.edu/~gasarch/BLOGPAPERS/Karp.pdf).
Removing empty sets and duplicate sets preserves whether an exact cover exists. Restricting to nonempty, distinct sets therefore causes no substantive difficulty.
Minor issue: the write-up then assumes \(u,n\geq1\), but deleting empty sets can leave \(n=0\) when the universe is nonempty. Such an instance is negative, whereas only the empty-universe case is explicitly handled.
Minimum clarification needed: explicitly account for the case in which no sets remain, or state why the chosen hard source restriction already excludes it. No new mathematical argument is needed.
Each element coordinate has matching counts \(c_e\) for value \(0\) and \(z\) for value \(1\). Types with ideal \(2\) match neither domain value, exactly as required by the task’s allowance for ideals outside current domains.
The two identical copies contribute
\(2\max(c_e,z)=c_e+z+|c_e-z|\).
Every padding coordinate for set \(C_j\) contributes \(y_j\) to the maximum matching count.
Consequently, the calculation
\(\sum_{\mathrm{block}\ i}M_i(S)=us+E(S)\)
is valid: the membership contribution \(\sum_j|C_j|y_j\) cancels the corresponding subtraction in the padding contribution. Hence
\(F_{\mathrm{block}}(S)=(h-u)s-E(S)\)
follows.
All padding multiplicities are nonnegative because \(C_j\subseteq U\). The block contains at least the \(2u\) element coordinates.
If \(z=0\), then \(E(S)=0\) requires every \(c_e=0\). Since every retained set is nonempty, selecting any set type would violate this requirement. Thus a nonempty zero-error subset must contain the anchor.
With \(z=1\), zero error requires \(c_e=1\) for every element. This is exactly the condition that the selected sets form an exact cover. The converse is also explicitly established.
The nonemptiness restriction on the source sets is used here and is sufficient. No condition on masses enters this correspondence.
Repeating every coordinate \(R=\tau\) times gives
\(F_D(S)/|S|=K-RE(S)/|S|\),
where \(K=R(h-u)\) is an integer.
In a positive source instance, a zero-error subset attains \(K\), and all subset averages are at most \(K\). Therefore \(B(D)=K\).
In a negative source instance, every nonempty subset has integer error at least \(1\). Since \(|S|\leq R\), every average is at most \(K-1\). Its ceiling is therefore also at most \(K-1\). The claimed equivalence with \(B(D)>K-1\) is exact.
The radius is valid: \(h-u\geq u\geq1\) ensures \(q=K-1\geq0\), and \(m-K=Ru>0\) ensures \(q\leq m\). There is no off-by-one error.
Since \(P\geq\tau=n+1\), the anchor numerator \(P-n\) is positive. The stated masses sum to \(1\), are dyadic, and have total encoding length \(O(\tau\log\tau)\).
The bounds
\(h\leq(n+2)u\)
and
\(m\leq(n+1)(n+2)u\)
are correct. Explicitly listing the complete ideal table requires polynomially many constant-size entries.
The construction respects every substantive input restriction: nonempty domains, complete ideals, positive masses, and the allowed radius range. Thus the reduction proves \(\mathrm{NP}\)-hardness of exact computation of \(B(D)\), and together with the certificates proves \(\mathrm{NP}\)-completeness of its threshold decision problem.
The appended coordinate contributes zero disagreement before fixing. Fixing it to \(1\) contributes exactly \(|S|\) disagreements for every subset. Therefore each subset average increases by \(1\), and its ceiling increases by \(1\). Both asserted bound identities follow.
With \(q'=K\), the initial bound always passes. Since \(B(D)\) is an integer at most \(K\), the condition \(B(D)+1>K\) is equivalent to \(B(D)=K\). The earlier reduction then gives exactly the claimed source-instance equivalence.
The extended radius is admissible, and every input domain still equals \(\{0,1\}\). This establishes the stronger removal-hardness claim without relying on an initially failing bound.
Gray-code updates change at most one matching count per coordinate. Scanning all domain counts and testing all input pairs costs \(O(md)\) arithmetic operations per nonempty subset. Taking the maximum ceiling and accumulating removal marks therefore gives exactly the requested output in \(O(md\,2^\tau)\) arithmetic operations after preprocessing.
The preprocessing estimate accounts for repeated comparisons of both ideal labels and domain labels. Its stated \(O((d+\tau)L)\) bound is conservative for explicitly encoded labels.
Subsequent counts, products, disagreement totals, and divisions involve integers of \(O(\log(m\tau+2))\) bits. The claimed schoolbook bit-time bound is therefore valid. Storing the counters, match information, and removal flags requires polynomial space.
Enumeration uses whole support types and never expands their masses into agents. The fixed-parameter tractability claim is consequently in the correct parameter, \(\tau\).
The only requested clarification concerns the omitted source preprocessing edge case. It does not undermine the reduction or the resulting hardness classification.
⟨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.