| paper | d4-conf-aaai-2010-0290 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
NP-hard→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{NP}\text{-complete}\) · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 2
statement extracted from the paper’s text layer
Given a required skill set \(S\), support types \(t=1,\ldots,\tau\) with skill bundles \(A_t\subseteq S\), positive rational masses \(\mu_t\) summing to one, and a rational threshold \(\rho\), let \(\mathcal Q\) be the inclusion-minimal type sets whose bundles cover \(S\). Does the LP maximizing \(\sum_{Q\in\mathcal Q}x_Q\), subject to \(x_Q\ge 0\) and \(\sum_{Q\ni t}x_Q\le\mu_t\) for every type \(t\), have optimum at least \(\rho\)?
A fractional packing of successful team profiles: each \(Q\in\mathcal Q\) is an inclusion-minimal set of types whose skill bundles cover \(S\), and \(x_Q\) is its rate of successful teams per unit of total population. Maximize \(\sum_Q x_Q\) subject to \(\sum_{Q\ni t}x_Q\le\mu_t\) for every type \(t\).
The convergence argument applies when the type catalog is fixed; it does not establish a uniform finite-to-limit guarantee for families where the support size grows with the population.
fatal: False
The mirror covers Theorem 2’s STSG NP-completeness result. It leaves Theorem 1’s representation result, Theorem 3’s restricted WTSG hardness, Theorem 4’s structural result, and Theorem 5’s bounded-treewidth algorithm without mirrors.
The strongest mirror I see is the per-capita rate of successful coalitions in a large, type-homogeneous population. Imagine a large response workforce handling many identical incidents: each worker has a skill bundle, and every team whose members collectively cover all required skills completes one incident. Many workers share each bundle, so the relevant input is the fraction of the workforce in each skill type.
My anchor is Theorem 2, proved in this paper: OPT-CS-STSG is NP-complete. The underlying decision problem takes a single-task skill game with one unit-weight task, agents who each have a set of skills, and a threshold \(r\). It asks whether the agents can be partitioned into coalitions whose total value is at least \(r\). The theorem proves NP-completeness by reducing from SET-SPLITTING: each set in the family becomes a skill, and the threshold is \(2\); the reduction makes two successful coalitions possible exactly when the elements can be split so every set meets both sides.
Here is the continuous problem I would hand to a prover. Let \(S\) be the set of required skills. The support consists of \(\tau\) agent types, where type \(t\) has skill set \(A_t\subseteq S\) and population fraction \(\mu_t>0\), with \(\sum_t\mu_t=1\). Let \(\mathcal C\) contain the inclusion-minimal sets \(Q\) of types whose skill bundles cover \(S\). A team of profile \(Q\) uses one agent of each type in \(Q\) and completes one task. For each \(Q\in\mathcal C\), choose a rate \(x_Q\ge0\), measured in successful teams per member of the total population. The problem STSG-Team-Density\(_\infty\) is to maximize \(\sum_{Q\in\mathcal C}x_Q\), subject to \(\sum_{Q\ni t}x_Q\le\mu_t\) for each type \(t\). Its decision version, STSG-Team-Density\(_\infty\)-Decision, also takes a rational threshold \(\rho\) and asks whether the maximum is at least \(\rho\). A solution is a feasible vector of team rates attaining that threshold, or an optimal such vector.
Minimal profiles suffice: adding a second agent of the same type, or any agent whose skills add nothing, cannot help a team complete the task. Leftover mass can form coalitions of value zero, just as unused agents can be placed in zero-value coalitions in the finite problem.
This has a direct high-multiplicity bridge. For fixed type fractions and a population of \(N\) agents with counts \(N\mu_t\), the finite optimum divided by \(N\) converges to this LP optimum as \(N\) grows. One direction follows because every finite partition gives a feasible rate vector. For the other, round down the number of teams prescribed by each \(x_Q\); the resource limits remain satisfied, and for a fixed type catalog the rounding loss is bounded while \(N\) grows. Thus the model keeps whole agents in whole teams while making the *rate of teams* continuous.
I think the authors would recognize this as their STSG coalition-structure problem in a repeated, high-multiplicity regime. The type is the complete relevant description of a worker—here, the skill bundle—and mass is the fraction of workers of that type. The objective still counts successful coalitions, just normalized by population size. The scenario requires abundant workers of each relevant type and many repeated task opportunities; it does not fit a small committee assigned to one unique event.
For the general case, I expect continuum-specific hardness (Class C), provisionally. The LP has potentially many team profiles, and dual pricing asks for a minimum-cost selection of types whose skill sets cover \(S\), which is weighted set cover. That is a serious obstacle to a general polynomial-time algorithm, though it is evidence rather than a hardness proof for the LP itself. When the number of skills \(k=|S|\) is fixed, minimal profiles have size at most \(k\), so they can be enumerated in polynomial time in \(\tau\); the open complexity lies in the general regime where the skill universe and support vary.
The continuous result is not implied by Theorem 2. Fractional team rates can change the answer: a finite instance may lack two disjoint successful teams even when its limiting rate LP admits a fractional combination of team profiles. The SET-SPLITTING reduction therefore does not automatically transfer. Establishing whether the continuous problem is polynomial-time solvable or NP-hard is a new question, and resolving it would say whether this anchor’s finite-population hardness survives continuization.
The scope here is deliberately just Theorem 2; I am not claiming a mirror for Theorem 3’s restricted WTSG hardness or Theorem 5’s bounded-treewidth algorithm. My weakest point is the shift from a finite optimum to its asymptotic per-capita rate, especially the repeated-incident interpretation. The convergence argument makes that shift precise for growing populations, but the paper’s NP-hardness result alone does not settle the continuous problem’s complexity.
The strongest objection is that the proposed mirror changes the paper’s finite-batch objective into a per-capita production rate. Theorem 2 asks whether one finite population can be partitioned to produce at least \(r\) successful coalitions; the density LP asks how many successful teams can be sustained per unit of population as that population grows. Its convergence argument is credible for a fixed type catalog, but that alone does not show the new question will illuminate the paper’s finite problem across growing families of instances.
That concern is limited, though. The change is exactly the high-multiplicity relaxation the programme sets out to study. Workers with the same skill bundle are indistinguishable for this problem, and each team consumes one worker of each type in its profile. The LP captures the resulting resource limits. A stronger version could use the same team-density formulation without the repeated-incident story: the STSG already awards one unit of value to every successful coalition, so its objective naturally counts successful teams.
Nor does the apparent computational difficulty defeat the mirror. Pricing the LP involves weighted set cover, which suggests the continuous problem may be hard; but that is a substantive complexity question, not evidence that the question is ill-posed or outside the programme. Restricting attention to fixed support would make the problem easy to enumerate, while allowing support to vary keeps a genuine computational landscape. The paper’s reduction may or may not transfer to this fractional setting, and finding out is a legitimate result either way.
So the negative case is weak. The mirror has a clear type definition, a plausible high-multiplicity setting, and a precise continuous optimization problem anchored in a named NP-completeness theorem. I cannot honestly argue that no worthwhile mirror exists here.
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.