Answer: \(\mathrm{NP}\)-hard under polynomial-time Turing reductions; in fact, undecidable under the stated evaluator assumptions.
Theorem 5.2 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateOn the class Ck(FP), the problems IN-CORE and CORE-NONEMPTINESS are co-NP-complete under randomized re- ductions. Hardness holds even for k = 2.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite set of candidate cohorts \(A\), rational masses \(\mu_a\) with \(\sum_{a\in A}\mu_a=1\), a succinct polynomial-time evaluator for a rational-valued worth function \(V\) on coalition mass vectors \(q\in\prod_{a\in A}[0,\mu_a]\), and a rational payoff-rate vector \(x\), decide whether \(\sum_{a\in A}\mu_a x_a=V(\mu)\) and \(\sum_{a\in A}q_a x_a\ge V(q)\) for every rational feasible \(q\). The input promises at most two hidden strategic types: \(a\) and \(b\) are equivalent exactly when, for every rational feasible base vector \(q\) and every positive rational \(\epsilon\) for which both additions are feasible, \(V(q+\epsilon e_a)=V(q+\epsilon e_b)\).
A society is given by its support: a nonempty list \(A\) of \(\tau\) observable cohort types with positive binary-rational masses \(\mu_a\), where \(\sum_{a\in A}\mu_a=1\). The support size \(\tau\) counts listed types, not possible types; these need not be distinct strategic types.
Let \(D=\prod_{a\in A}([0,\mu_a]\cap\mathbb Q)\). The input includes a succinct evaluator for \(V:D\to\mathbb Q\), computing exact values in time polynomial in its description length and the query's binary length, and payoff rates \(x\in\mathbb Q^A\). Worths and rates may have either sign; no continuity, monotonicity, or convexity is assumed.
For \(a,b\in A\), define \(a\sim b\) precisely when \(V(q+\epsilon e_a)=V(q+\epsilon e_b)\) for every \(q\in D\) and positive rational \(\epsilon\) for which both additions lie in \(D\); \(e_a\) is the coordinate unit vector. Promise that this relation is an equivalence relation with at most two classes; their partition is not supplied.
The decision problem accepts precisely when \(\sum_{a\in A}\mu_a x_a=V(\mu)\) and \(\sum_{a\in A}q_a x_a\ge V(q)\) for every \(q\in D\), including \(q=0\). Rates need not agree across strategically equivalent cohorts.
Let \(m\) be the evaluator description length and \(L\) the total input bit length. State running times in \(m,\tau,L\); evaluation uses a fixed uniform polynomial bound, and coalition denominators have no imposed bound.
Is this promised continuous core-membership problem in \(\mathrm P\), or is it \(\mathrm{NP}\)-hard under polynomial-time Turing reductions?
Discrete core membership and core nonemptiness with polynomial-time worth evaluation and unknown strategic types are \(\mathrm{coNP}\)-complete under randomized reductions, even with at most two types; with a supplied partition into a fixed number of types, both are polynomial-time solvable. [Discrete results](https://doi.org/10.3233/978-1-61499-098-7-372).
No result settling this exact rational-mass evaluator problem was located.
The problem is \(\mathrm{NP}\)-hard under polynomial-time Turing reductions. This holds even with exactly three observable cohorts, exactly two strategic classes, unequal rates within a strategic class, and a continuous piecewise affine worth function.
Under the full evaluator assumptions in the question, the problem is in fact undecidable. Both claims are proved below.
Fix three cohorts with masses \(\mu=(1/4,1/4,1/2)\) and rates \(x=(0,1,2)\). For a coalition \(q\), write \(s=q_1+q_2\) and \(z=q_3\). Define \(B(s)=\max\{0,s-1/4\}\).
Let \(H:[0,1/2]\cap\mathbb Q\to\mathbb Q\) satisfy \(H(0)=H(1/2)=0\), and define
\(V_H(q)=B(s)+2z+H(s)\).
Efficiency. At the grand coalition, \(s=1/2\) and \(z=1/2\). Consequently,
\(V_H(\mu)=1/4+1=5/4=\sum_a\mu_a x_a\).
Coalitional inequalities. Because \(q_1\le 1/4\), we have \(q_2=s-q_1\ge s-1/4\). Together with \(q_2\ge0\), this gives \(q_2\ge B(s)\). Therefore
\(\sum_a q_a x_a-V_H(q)=q_2-B(s)-H(s)\).
For each rational \(s\in[0,1/2]\), the feasible coalition
\(q^{(s)}=(\min\{s,1/4\},B(s),0)\)
has total first-class mass \(s\) and satisfies \(q^{(s)}_2=B(s)\). It follows that
\(x\) belongs to the core if and only if \(H(s)\le0\) for every rational \(s\in[0,1/2]\).
Indeed, if all these inequalities hold, the displayed payoff difference is nonnegative for every coalition. If \(H(s)>0\), the coalition \(q^{(s)}\) has payoff difference \(-H(s)<0\). The zero coalition is included: its worth and payoff are both zero.
Strategic classes. Cohorts \(1\) and \(2\) are equivalent under the precise definition in the question: adding any feasible common increment to either coordinate changes \(s\) by the same amount and leaves \(z\) unchanged.
Suppose there is a rational \(\epsilon\in(0,1/4]\) with \(H(\epsilon)\ne2\epsilon\). At \(q=0\),
\(V_H(\epsilon e_1)=V_H(\epsilon e_2)=H(\epsilon)\),
whereas \(V_H(\epsilon e_3)=2\epsilon\).
Thus neither cohort \(1\) nor cohort \(2\) is equivalent to cohort \(3\). The relation is therefore exactly the equivalence relation with classes \(\{1,2\}\) and \(\{3\}\). Notice that the equivalent cohorts have different rates.
Both constructions below meet this additional condition.
Let \(F\) be a Boolean formula on \(n\) variables, and set \(N=2^n\). For each integer \(k\) with \(0\le k<N\), let \(b(k)\) be its \(n\)-bit assignment, with leading zeros included.
Define \(H_F(1/2)=0\). For rational \(s\in[0,1/2)\), compute
\(t=2Ns\), \(k=\lfloor t\rfloor\), and \(r=t-k\), and set
\(H_F(s)=F(b(k))\min\{2r,2-2r\}\),
interpreting the Boolean formula value as either zero or one.
This function is nonnegative. On each interval \([k/(2N),(k+1)/(2N)]\), it is either zero or a triangular tent of height one. Every tent vanishes at both endpoints. Hence the definitions agree at all interval boundaries, and \(H_F\) extends to a continuous piecewise affine function on the real interval \([0,1/2]\). In particular, \(H_F(0)=H_F(1/2)=0\).
If \(F\) is unsatisfiable, then \(H_F\) is identically zero. If assignment \(b(k)\) satisfies \(F\), the rational midpoint \(s_k=(2k+1)/(4N)\) satisfies \(H_F(s_k)=1\). Thus
\(H_F(s)\le0\) for every rational \(s\in[0,1/2]\) if and only if \(F\) is unsatisfiable.
Apply the construction of Section 1 with \(H=H_F\). Its efficiency and coalitional calculations show that the resulting core-membership instance accepts exactly when \(F\) is unsatisfiable.
The strategic-type promise also holds. Choose \(\epsilon=1/(4N)\). This lies in \((0,1/4]\), and it is the midpoint of the first tent. Consequently \(H_F(\epsilon)\in\{0,1\}\), while \(2\epsilon=1/(2N)\) lies strictly between zero and one. Therefore \(H_F(\epsilon)\ne2\epsilon\), proving that there are exactly two classes.
Finally, the evaluator is succinct and uniformly polynomial-time. It stores \(F\), computes one index \(k\) by exact rational arithmetic, evaluates \(F\) on that assignment, and computes the tent height. Although there are \(N\) potential tents, evaluation never enumerates them: the integer \(2N\) has only \(n+2\) binary digits.
This is a polynomial-time many-one reduction from unsatisfiability to core membership. To decide satisfiability using a core-membership oracle, construct this instance, make one query, and negate its answer. Hence core membership is \(\mathrm{NP}\)-hard under polynomial-time Turing reductions.
Moreover, \(V_{H_F}\) is continuous and piecewise affine, since every term in its definition has those properties.
The absence of any bound on coalition denominators permits a stronger reduction.
Let \(M\) be an arbitrary deterministic Turing machine started on a blank tape. For a rational \(s\), let \(d(s)\) denote the binary length of its positive denominator in lowest terms. Define \(H_M(0)=H_M(1/2)=0\). At every other rational \(s\in(0,1/2)\), define \(H_M(s)=1\) if \(M\) halts within \(d(s)\) simulated steps, and \(H_M(s)=0\) otherwise.
Polynomial-time evaluation. Given a coalition query, compute and reduce \(s=q_1+q_2\). Its denominator has bit length bounded by the query’s total bit length. Simulating \(M\) for \(d(s)\) steps takes time polynomial in that length and the description length of \(M\), using a fixed universal simulation algorithm. Thus this evaluator satisfies the required fixed uniform polynomial bound. It always terminates, including when \(M\) never halts.
Apply Section 1 with \(H=H_M\). The strategic-type promise holds with \(\epsilon=1/4\): \(H_M(1/4)\in\{0,1\}\), whereas \(2\epsilon=1/2\).
If \(M\) never halts, then \(H_M\) is identically zero, so the instance accepts.
If \(M\) halts after \(T\) steps, choose an integer \(k\ge\max\{3,T\}\) and set \(s=2^{-k}\). This is an interior rational point whose reduced denominator has binary length \(k+1\). Therefore \(H_M(s)=1\), and the coalition \(q^{(s)}\) from Section 1 violates its core inequality. The instance rejects.
The construction consequently satisfies:
the core-membership instance accepts if and only if \(M\) never halts.
Any algorithm deciding these promised core-membership instances would therefore decide blank-tape halting by negating its answer. This contradicts the classical undecidability theorem for halting. Every constructed instance has a total polynomial-time evaluator and exactly the required two strategic classes, so the reduction stays inside the promise.
Let \(\ell\) denote the total binary length of a coalition query. Both evaluator families run in time \(O((m+\tau+\ell)^c)\) for some fixed absolute constant \(c\), independent of the encoded formula or machine.
Both reductions use \(\tau=3\). Their descriptions and total instance lengths \(m,L\) are polynomial in the source description length, and construction takes polynomial time. In particular, a core-membership algorithm polynomial in \(m,\tau,L\) would yield a polynomial-time satisfiability algorithm.
For the unrestricted model posed in the question, the halting reduction rules out any deciding algorithm, regardless of its running time. The supplied discrete results are not needed: even supplying the partition \(\{\{1,2\},\{3\}\}\) would leave both reductions intact.
⟨structured verdict parsed — rendered above⟩
The prover resolves the requested complexity question. The reduction establishes \(\mathrm{NP}\)-hardness under polynomial-time Turing reductions, and the additional undecidability argument is valid under the stated evaluator model. No major or minor mathematical gaps were found.
The masses \(\mu=(1/4,1/4,1/2)\) are positive binary rationals and sum to one. The rates \(x=(0,1,2)\) are admissible, including the unequal rates assigned to cohorts \(1\) and \(2\).
For every feasible coalition, \(s=q_1+q_2\) belongs to \([0,1/2]\cap\mathbb Q\). Thus all evaluations of \(H(s)\) are within its specified domain.
The efficiency calculation is correct:
\[
V_H(\mu)=B(1/2)+1+H(1/2)=1/4+1=5/4,
\]
which equals the grand-coalition payoff.
The coalitional payoff difference is exactly
\[
q_2-B(s)-H(s).
\]
The inequalities \(q_2\geq 0\) and \(q_2=s-q_1\geq s-1/4\) imply \(q_2\geq B(s)\).
The proposed coalition \(q^{(s)}\) is feasible throughout the entire interval:
In both cases, its first two coordinates sum to \(s\), and its payoff difference is \(-H(s)\). Consequently, the asserted equivalence between core membership and universal nonpositivity of \(H\) is justified in both directions. The endpoint assumptions also correctly handle the zero coalition.
Cohorts \(1\) and \(2\) satisfy the exact universal definition of equivalence: every common feasible increment produces the same arguments \(s+\epsilon,z\) for \(V_H\).
For the proposed distinguishing increment, \(B(\epsilon)=0\) because \(0<\epsilon\leq 1/4\). Therefore the displayed values at \(q=0\) are correct. All three increments are feasible under the specified masses.
A single unequal evaluation suffices to disprove each claimed equivalence with cohort \(3\). Together with reflexivity and symmetry, and the established equivalence of cohorts \(1\) and \(2\), this gives exactly the partition \(\{\{1,2\},\{3\}\}\). There is no unverified transitivity assumption.
For \(s<1/2\), the computed index satisfies \(0\leq k<N\), so the assignment \(b(k)\) is always defined. The fractional part satisfies \(0\leq r<1\), and the tent height is nonnegative.
The continuity claim is correct. Within each indexed interval, the function is piecewise affine. Both neighboring pieces approach zero at a shared interval boundary, where the evaluator also returns zero. The separately defined value at \(1/2\) agrees with the left limit.
At the proposed midpoint,
\[
2Ns_k=k+1/2,
\]
so the tent height is exactly one. Thus a satisfying assignment gives a rational violating coalition, while unsatisfiability makes \(H_F\) identically zero.
The strategic-class witness also works: \(\epsilon=1/(4N)\) is feasible, \(H_F(\epsilon)\) is either zero or one, and \(2\epsilon=1/(2N)\) is strictly between them. This remains valid if the source formula has no variables.
The succinctness argument is sound. The evaluator stores the formula and uses integers with bit lengths polynomial in the formula length and query length. It does not enumerate the exponentially many intervals. Exact rational arithmetic, extraction of the assignment bits, and Boolean-formula evaluation all have polynomial cost.
The reduction maps unsatisfiability to acceptance. Negating one oracle answer therefore decides satisfiability. Using the standard \(\mathrm{NP}\)-completeness of Boolean satisfiability, this establishes precisely the requested polynomial-time Turing hardness; the prover does not confuse this with a many-one reduction from satisfiability.
The denominator-based definition is well-defined because it uses the unique reduced positive denominator. The endpoint overrides explicitly guarantee the assumptions required by the common construction.
Adding two query rationals and reducing their sum takes polynomial time. The reduced denominator divides the product of the input denominators, so its bit length is bounded by the total query bit length. Simulating an encoded deterministic machine for that many steps admits a fixed polynomial bound in the machine-description length and query length. The evaluator therefore remains total and uniformly polynomial-time even when the encoded machine never halts.
The strategic-class witness \(\epsilon=1/4\) is valid independently of the machine’s behavior: \(H_M(1/4)\in\{0,1\}\), whereas \(2\epsilon=1/2\).
If the machine never halts, all values of \(H_M\) are zero. If it halts after \(T\) steps, the selected \(s=2^{-k}\) is an interior rational, and its reduced denominator has bit length \(k+1\geq T\). Hence its value is one and the corresponding coalition violates the core inequality.
The reduction is effective and stays entirely within the promise. A decider for these instances would decide blank-tape halting by complementing its answer, contradicting the standard undecidability theorem. The unrestricted-denominator assumption permits exactly the arbitrarily long queries used here.
The claimed fixed polynomial evaluation bounds are justified for both families. Both instance constructions have \(\tau=3\), and their evaluator descriptions and total input lengths are polynomial in their source-description lengths.
The continuous piecewise affine restriction applies to the formula construction. The undecidability construction uses the unrestricted evaluator assumptions. The prover keeps these claims distinct and establishes both.
No repair or additional clarification 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.