d4-conf-sigecom-2012-0028 (d4-conf-sigecom-2012-0028)

Given a finite set of roles \(T\), rational masses \(\mu_t>0\) summing to \(1\), a symmetric interaction matrix \(A\) with zero diagonal, signal probability \(p\), and threshold \(c\), choose a schedule fixed before signals are known. The schedule is a finite sequence of role blocks whose durations sum to \(\mu_t\) for each \(t\). If \(y_u\) and \(n_u\) are the \(Y\)- and \(N\)-masses in role \(u\), a type-\(t\) block faces margin \(D_t=\sum_{u:A_{tu}=1}(y_u-n_u)/\mu_u\); it chooses \(Y\) when \(D_t\ge c\), \(N\) when \(D_t\le -c\), and otherwise splits according to the signal proportions \(p\) and \(1-p\). What is the complexity of finding a schedule whose final \(Y\)-mass is within additive \(\epsilon\) of the supremum, measured in \(\tau=|T|\), input bit length, \(c\), and \(\log(1/\epsilon)\)?

A society is given by its support: a nonempty list of \(\tau\) roles \(T\), each with positive binary rational mass \(\mu_t\), with \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types; the number of roles is \(m=\tau\).
The input also contains a symmetric matrix \(A\in\{0,1\}^{\tau\times\tau}\) with zero diagonal, a binary rational \(p\in(0,1)\), an integer threshold \(c\ge1\), and a binary rational tolerance \(\epsilon\in(0,1)\). Let \(L\) be the total binary input length.
A schedule is a finite sequence \(S=((t_i,d_i))_{i=1}^k\), fixed in advance, with positive rational durations and \(\sum_{i:t_i=t}d_i=\mu_t\) for every role; roles may recur and there is no prescribed bound on \(k\).
Initially \(y_t=n_t=0\). Before a block \((t,d)\), compute \(D_t=\sum_{u:A_{tu}=1}(y_u-n_u)/\mu_u\) using only mass processed earlier.
The block adds \((d,0)\) to \((y_t,n_t)\) if \(D_t\ge c\), adds \((0,d)\) if \(D_t\le-c\), and otherwise adds \((pd,(1-p)d)\). These splits are deterministic signal proportions; decisions are irreversible, and equality at either threshold follows the corresponding majority.
Write \(V(S)=\sum_t y_t\) for the final favorable mass and \(\mathrm{OPT}=\sup_S V(S)\) over these finite schedules.

Is finding a schedule \(S\) with \(V(S)\ge\mathrm{OPT}-\epsilon\) possible in time polynomial in \(m,\tau,L,c,\log(1/\epsilon)\), or is this problem NP-hard?

For discrete agents with independent positive signals of probability \(p\), fixed integer \(c\ge2\), and sufficiently small fixed \(\eta>0\), distinguishing optimal non-adaptive expected adoption at least \(np^{1+\eta}\) from at most \(np^{c-\eta}\) is NP-hard when \(p\) is inverse polynomial in \(n\). [Discrete gap hardness](https://www.cs.cornell.edu/home/kleinber/ec12-cascade.pdf)
No result settling this exact normalized, divisible-mass scheduling problem was located in the literature search.

Result

The problem is NP-hard, even with fixed \(c=2\), fixed \(p=1/4\), and uniform masses. The reduction applies to every finite schedule, regardless of its number of blocks.

Consequently, an algorithm with the requested polynomial running time would imply \(\mathrm{P}=\mathrm{NP}\).

1. Source problem and construction

We reduce from Independent Set: given a finite simple undirected graph \(G\) with \(n\) vertices and an integer \(k\) satisfying \(1\le k\le n\), decide whether its independence number \(\alpha(G)\) satisfies \(\alpha(G)\ge k\). This decision problem is NP-complete.

We may assume that \(n\) is a power of two. Indeed, adding isolated vertices until the vertex count reaches the next power of two, and increasing \(k\) by the number added, preserves the answer and increases the instance size by at most a constant factor.

Set \(M=8n\). Replace each vertex \(v\) of \(G\) by a group \(C_v\) of \(M\) roles. There are no edges within a group. For distinct vertices \(v,w\), connect every role in \(C_v\) to every role in \(C_w\) precisely when \(vw\) is an edge of \(G\).

The resulting society has parameters

\(m=\tau=nM=8n^2,\qquad \mu_t=1/(nM),\qquad p=1/4,\qquad c=2,\qquad \epsilon=1/(32n).\)

Its adjacency matrix is symmetric with zero diagonal. All masses are positive and sum to one. Because \(n\) is a power of two, the masses and tolerance are even dyadic rationals.

2. Monotonicity and favorable mass

Fix any finite schedule for the constructed society.

For every role, the imbalance \(y_t-n_t\) remains nonpositive. To prove this, initially all imbalances vanish. If all imbalances are nonpositive before a block, then \(D_t\le0\), so the favorable-majority condition \(D_t\ge2\) cannot hold. The block therefore either:

• follows the deterministic signal proportions, adding imbalance \((2p-1)d=-d/2\); or
• follows the negative majority, adding imbalance \(-d\).

Both updates preserve nonpositive imbalances, completing the induction.

Call a block neutral when it follows the signal proportions. Thus a neutral block has \(-2<D_t\le0\).

For each role \(t\), let \(z_t\) be the fraction of its mass processed in neutral blocks:

\(z_t=\mu_t^{-1}\sum_{i:\,t_i=t,\ i\text{ neutral}}d_i.\)

Since the schedule processes exactly mass \(\mu_t\) of role \(t\), we have \(0\le z_t\le1\). Neutral blocks contribute favorable proportion \(p=1/4\), while negative-majority blocks contribute no favorable mass. Therefore

\(V(S)=\frac14\sum_t\mu_tz_t=\frac{1}{4nM}\sum_tz_t.\)

We also need a bound valid at intermediate times. Define the normalized negative imbalance by \(x_t=(n_t-y_t)/\mu_t\). If fractions \(a_t\) and \(b_t\) of role \(t\) have already been processed neutrally and by negative majority, respectively, then

\(x_t=\frac12a_t+b_t\ge\frac12a_t.\)

In particular, negative-majority processing can only strengthen the negative influence used below.

3. Large neutral groups form an independent set

For each original vertex \(v\), define

\(F_v=\sum_{t\in C_v}z_t.\)

Thus \(0\le F_v\le M\). Let

\(I(S)=\{v:F_v\ge4\}.\)

Lemma. For every finite schedule \(S\), the set \(I(S)\) is independent in \(G\).

Proof. Suppose that adjacent vertices \(v,w\) both belong to \(I(S)\). Each group has positive neutral processing, so each has a last neutral block. These last blocks exist because the schedule is finite.

Without loss of generality, the last neutral block in \(C_v\) occurs before the last neutral block in \(C_w\). Let the latter block process role \(t\in C_w\).

Immediately before this block, all neutral processing in \(C_v\) has finished. The intermediate-time inequality from Section 2 therefore gives

\(\sum_{u\in C_v}x_u\ge\frac12\sum_{u\in C_v}z_u=\frac12F_v\ge2.\)

Every role in \(C_v\) is adjacent to \(t\), and all other normalized negative imbalances are nonnegative. Consequently,

\(D_t=-\sum_{u:A_{tu}=1}x_u\le-\sum_{u\in C_v}x_u\le-2.\)

The block must therefore follow the negative majority, including at equality. This contradicts its being neutral. Hence adjacent vertices cannot both belong to \(I(S)\). \(\square\)

This proof uses neither a bound on the number of blocks nor any restriction on their rational durations.

4. Bounds on the optimum

The lemma gives an upper bound for every schedule. Groups indexed by \(I(S)\) have \(F_v\le M\); all remaining groups have \(F_v<4\). Hence

\(\sum_vF_v\le |I(S)|M+4n.\)

Substituting into the favorable-mass formula and using \(M=8n\), we obtain

\(V(S)\le\frac{|I(S)|}{4n}+\frac{1}{8n}\le\frac{\alpha(G)}{4n}+\frac{1}{8n}.\)

For a lower bound, take any independent set \(J\) in \(G\). First process every role in every group \(C_v\) with \(v\in J\), using one full-mass block per role. During this part of the schedule, every processed role has \(D_t=0\): there are no edges within a group or between groups indexed by \(J\). All these blocks are neutral.

Complete the schedule by processing the remaining roles in any order. Favorable mass already obtained is irreversible, so this schedule satisfies

\(V(S)\ge\frac{|J|}{4n}.\)

Taking a maximum independent set yields the proved bounds

\(\frac{\alpha(G)}{4n}\le\mathrm{OPT}\le\frac{\alpha(G)}{4n}+\frac{1}{8n}.\)

The upper bound holds for every finite schedule, so it also holds for their supremum. No attainment assumption is needed.

5. A near-optimal schedule decides Independent Set

Suppose an algorithm returns a schedule \(S\) satisfying

\(V(S)\ge\mathrm{OPT}-\epsilon,\qquad \epsilon=\frac{1}{32n}.\)

Simulate this schedule and construct \(I(S)\) as above.

If \(\alpha(G)\ge k\), the lower bound gives

\(V(S)\ge\frac{k}{4n}-\frac{1}{32n}.\)

If nevertheless \(|I(S)|\le k-1\), the schedule-specific upper bound would give

\(V(S)\le\frac{k-1}{4n}+\frac{1}{8n}=\frac{k}{4n}-\frac{1}{8n}.\)

These inequalities are incompatible because \(1/(32n)<1/(8n)\). Thus \(|I(S)|\ge k\).

Conversely, if \(\alpha(G)<k\), the lemma guarantees \(|I(S)|<k\) for every schedule.

Therefore, checking whether \(|I(S)|\ge k\) decides the Independent Set instance.

6. Polynomial size and conclusion

The constructed society has \(8n^2\) roles, and its explicit adjacency matrix has \(64n^4\) entries. Each mass and the tolerance require \(O(\log n)\) bits. Thus the construction has polynomial binary length, with fixed \(c=2\) and \(\log(1/\epsilon)=O(\log n)\).

Under the ordinary explicit representation of a schedule, a polynomial-time algorithm can output only polynomially many bits. Such an output can be simulated exactly in polynomial time: all state updates and threshold comparisons use rational arithmetic, whose intermediate bit lengths are bounded polynomially by the input and output lengths. This also computes each \(F_v\) and the set \(I(S)\).

Hence the proposed polynomial-time approximation algorithm would yield a polynomial-time algorithm for Independent Set. This proves NP-hardness directly for the normalized divisible-mass model; the cited discrete gap theorem is not needed.

⟨structured verdict parsed — rendered above⟩

The prover’s NP-hardness claim is correct. The reduction addresses the exact normalized, divisible-mass model and remains valid for every finite schedule, including schedules with arbitrarily many blocks. No mathematical gaps or incorrect steps were found.

• Source problem and padding.

Independent Set is correctly stated for finite simple undirected graphs with \(1\le k\le n\). Adding \(r\) isolated vertices increases the independence number by exactly \(r\), so replacing \(k\) by \(k+r\) preserves the decision answer. Padding to the next power of two increases the vertex count by less than a factor of two.

The construction produces \(nM=8n^2\) roles, each with mass \(1/(nM)\). Their masses sum to one. The constructed adjacency matrix is symmetric and has zero diagonal. The chosen parameters satisfy all domain restrictions, including when \(n=1\). The dyadic-rational assertion is also correct.

• Nonpositive imbalances and favorable mass.

The induction proving \(y_t-n_t\le0\) is valid. Under its inductive hypothesis, every summand defining \(D_t\) is nonpositive, so favorable-majority processing cannot occur. Neutral processing changes the imbalance by \(-d/2\), and negative-majority processing changes it by \(-d\).

Consequently, the characterization of neutral blocks as those with \(-2<D_t\le0\) is exact. In particular, it respects the rule that equality at \(-2\) triggers negative majority.

The definitions and identities
\[ 0\le z_t\le1,\qquad V(S)=\frac{1}{4nM}\sum_t z_t,\qquad x_t=\frac12a_t+b_t\ge\frac12a_t \]
follow directly from the prescribed updates. They hold at the intermediate times used later.

• The independent-set lemma.

This is the central step, and it is sound.

If two adjacent groups both have \(F_v\ge4\), each has a last neutral block because the schedule is finite and its total neutral processing is positive. Their last neutral blocks occupy distinct positions in the sequence, so one precedes the other.

Immediately before the later block, all neutral processing in the earlier group has finished. Thus the stated intermediate-time inequality yields
\[ \sum_{u\in C_v}x_u\ge\frac12F_v\ge2. \]
Complete adjacency between the two groups and nonnegativity of all other \(x_u\) then imply \(D_t\le-2\). The later block must therefore be negative-majority, contradicting its designation as neutral.

There is no dependence on a bound on the number of blocks, on minimum durations, or on attainment of the supremum.

• Bounds on the optimum.

Since \(I(S)\) is independent, \(|I(S)|\le\alpha(G)\). The group bounds imply
\[ \sum_vF_v\le |I(S)|M+4n, \]
and the resulting arithmetic is correct:
\[ V(S)\le\frac{|I(S)|}{4n}+\frac{1}{8n}. \]

The lower-bound schedule is valid. While processing groups corresponding to an independent set, every neighbor of the currently processed role remains unprocessed. Hence \(D_t=0\), and every such block is neutral. Completing the schedule cannot remove favorable mass already obtained.

Both claimed optimum bounds follow. Passing the universal upper bound to the supremum is justified without assuming an optimal schedule exists.

• Recovery from an approximate schedule.

In a yes-instance, the approximation guarantee gives
\[ V(S)\ge\frac{k}{4n}-\frac{1}{32n}. \]
If \(|I(S)|\le k-1\), the schedule-specific upper bound gives
\[ V(S)\le\frac{k}{4n}-\frac{1}{8n}. \]
These bounds contradict one another: their separation is \(3/(32n)>0\).

In a no-instance, the independent-set lemma guarantees \(|I(S)|<k\) for every schedule. Thus the proposed decision procedure works in both directions, including the endpoint cases \(k=1\) and \(k=n\).

• Polynomial size and exact simulation.

The role count and matrix-entry count are correctly calculated as \(8n^2\) and \(64n^4\). All parameter encodings have polynomial length.

The explicit-output assumption matches the requested finite sequence of rational blocks. A polynomial-time algorithm can output only polynomially many bits. Exact simulation uses rational additions and multiplication or division by fixed input rationals; intermediate bit lengths are polynomial in the combined input and schedule-output lengths. Threshold comparisons, neutral-block identification, and computation of \(I(S)\) therefore take polynomial time.

The reduction establishes that the requested approximation algorithm would decide Independent Set in polynomial time. The supplied discrete hardness result is not used and requires no verification for this argument.

Actionable feedback: None required. The write-up resolves its claim as stated.

⟨structured verdict parsed — rendered above⟩