Answer: \(\mathrm{NP}\)-hard; the deterministic-response restriction is \(\mathrm{NP}\)-complete, and the general problem belongs to \(\mathrm{PSPACE}\).
Proposition 1 — class: other
Given finite \(D\), \(S\), and \(T\), rational masses \(\mu_t\) summing to \(1\), rational type utilities \(u_t\), outcome distributions, response probabilities, query costs, discount factor, horizon \(H\), and value threshold \(\eta\), is there a history-contingent policy choosing standard-gamble queries \(q_i(l)\), with rational \(l\in[0,1]\), or terminal decisions, whose expected discounted per-capita utility minus query costs is at least \(\eta\)? At each response history \(h\), querying type mass \(x_{h,t}\) splits it as \(x_{h,r,t}=x_{h,t}\Pr(r\mid q_i(l),u_t)\).
Let \(D\) and \(S=\{s_1,\ldots,s_m\}\) be nonempty finite sets of terminal decisions and outcomes. Each decision has an explicitly given rational outcome distribution \(p_d\); type \(t\) has rational utilities \(u_t:S\to[0,1]\), giving terminal reward \(R(d,t)=\sum_i p_d(s_i)u_t(s_i)\).
A society is given by its support: the list \(T\) of its \(\tau\) types with positive binary-rational masses \(\mu_t\), summing to \(1\). Here \(\tau\) is the support size, not the number of possible types; type remains unchanged throughout elicitation and is unobserved by the policy.
A standard-gamble query \(q_i(l)\), with rational \(l\in[0,1]\), compares \(s_i\) with reference prizes of utilities \(1\) and \(0\), received with probabilities \(l\) and \(1-l\). The reference prizes need not belong to \(S\).
Input rational error rates \(a_i,b_i\in[0,1]\) determine \(P(\mathrm{yes}\mid q_i(l),t)=a_i\) if \(u_t(s_i)<l\), and \(1-b_i\) otherwise; the probability of no is complementary. Responses are conditionally independent given type and queries.
Each query \(q_i(l)\) costs \(c_i\geq0\) per unit mass, independently of type and \(l\). Costs, discount \(\gamma\in(0,1)\), and threshold \(\eta\in\mathbb Q\) are binary rationals; the nonnegative integer query horizon \(H\) is encoded in unary.
A deterministic policy assigns one query or terminal decision to each response history, uses at most \(H\) queries on every path, and then terminates. Starting from \(x_{\varnothing,t}=\mu_t\), a queried node \(h\) splits its entire mass by \(x_{hr,t}=x_{h,t}P(r\mid q_i(l),t)\); actions cannot depend on the unobserved type.
Its value is \(V(\pi)=\sum_{h\text{ terminal}}\gamma^{|h|}\sum_t x_{h,t}R(d_h,t)-\sum_{h\text{ queried}}\gamma^{|h|}c_{i_h}\sum_t x_{h,t}\). Let \(L\) be the total input bit length; state running times in \(m,\tau,|D|,H,L\).
Is deciding whether there exists such a policy with \(V(\pi)\geq\eta\) in \(\mathrm P\), or is it \(\mathrm{NP}\)-hard?
[Boutilier (2002)](https://www.cs.toronto.edu/~cebly/Papers/_download_/pefa.pdf) states mixture linearity of optimized query values, but supplies no discrete complexity classification.
[Conitzer and Sandholm (2003)](https://www.cs.cmu.edu/~conitzer/metareasoningIJCAI03.pdf) prove finite-state STATE-DISAMBIGUATION \(\mathrm{NP}\)-hard even with deterministic responses, and \(\mathrm{PSPACE}\)-hard generally; its reward requires certain identification, unlike the terminal rewards here.
No complexity classification for exactly the mass problem defined above was located.
Classification. The problem is \(\mathrm{NP}\)-hard under polynomial-time many-one reductions, even with deterministic responses, utilities in \(\{0,1\}\), and \(|D|=2\). The deterministic-response restriction is \(\mathrm{NP}\)-complete. The general problem belongs to \(\mathrm{PSPACE}\).
The proof below uses the stipulated terminal rewards directly.
1. Reduction from Set Cover. Consider a Set Cover instance with nonempty universe \(U=\{e_1,\ldots,e_N\}\), subsets \(A_1,\ldots,A_M\), and budget \(k\). The question is whether at most \(k\) subsets cover \(U\). We may restrict to \(M\geq1\) and \(1\leq k\leq M\): the excluded cases are trivial, and budgets exceeding \(M\) can be capped at \(M\).
We may also delete elements with duplicate incidence vectors, since this preserves the existence of a cover. Thus the constructed element types below are distinct.
The construction follows the distinguished-state idea in [Conitzer and Sandholm, Theorem 3](https://www.cs.cmu.edu/~conitzer/metareasoningIJCAI03.pdf), but replaces their identification reward with two permitted terminal decisions.
Choose powers of two \(B,C\) satisfying
\(N+1\leq B<2(N+1),\qquad 4B(k+1)\leq C<8B(k+1).\)
Construct the following instance.
\(\mu_{t_0}=(B-N)/B\) and \(\mu_{t_j}=1/B\) for \(1\leq j\leq N\).
The outcomes \(z,w\) are ordinary outcomes with type-dependent utilities; the fixed reference prizes remain external.
All masses are positive dyadic rationals and sum to \(1\). Every positive type mass is at least \(1/B\). The terminal rewards are exactly
\(R(d_0,t_0)=1,\quad R(d_1,t_0)=0,\quad R(d_0,t_j)=0,\quad R(d_1,t_j)=1\quad(j\geq1).\)
Thus correct classification earns \(1\), and incorrect classification earns \(0\).
For a membership outcome \(s_i\), any threshold \(l\in(0,1]\) produces yes exactly for the types whose elements belong to \(A_i\). At \(l=0\), every type answers yes. Consequently, allowing arbitrary rational thresholds introduces no additional informative partitions.
Bernoulli’s inequality gives
\(\eta=(1-1/C)^k\geq1-k/C>1-1/(4B)>1-1/B.\)
In particular, \(\eta>1/2\).
2. Reward-outcome queries cannot bypass the construction. Because responses are deterministic, each type follows a unique path. At every reachable node, its mass vector consists of the original masses of the types reaching that node. Hence the total mass of a reachable node is at least \(1/B\).
Suppose a policy queries \(z\) or \(w\) at a reachable node of depth \(d\). Its discounted cost at that node is at least
\(\gamma^d(2B)(1/B)=2\gamma^d\geq2\gamma^k=2\eta>1.\)
The policy’s total discounted terminal reward is at most \(1\): every type terminates once, every reward is at most \(1\), and the masses sum to \(1\). All other costs are nonnegative. Therefore this policy has value strictly below \(0\), and cannot reach the positive threshold \(\eta\).
It follows that every policy reaching \(\eta\) uses only membership queries at reachable nodes.
3. A set cover yields a qualifying policy. Suppose \(A_{i_1},\ldots,A_{i_r}\) cover \(U\), where \(r\leq k\).
Ask their membership queries in order, using threshold \(1/2\). After the first yes response, terminate with \(d_1\). If all responses are no, terminate with \(d_0\).
Every element type eventually answers yes because the selected sets cover \(U\), and receives reward \(1\). The distinguished type always answers no and also receives reward \(1\). Every path has at most \(k\) queries, and all queried costs are zero. Consequently,
\(V(\pi)=\sum_t\mu_t\gamma^{\ell_t}\geq\sum_t\mu_t\gamma^k=\eta,\)
where \(\ell_t\leq k\) is the terminal depth for type \(t\).
4. A qualifying policy yields a set cover. Suppose no collection of at most \(k\) sets covers \(U\), and consider any policy that could reach \(\eta\). By Section 2, its reachable queries must be membership queries.
Follow the unique path taken by \(t_0\). Let \(I\) be the indices of membership outcomes queried on this path with positive thresholds. There are at most \(k\) such indices. By assumption, some element \(e_j\) lies outside \(\bigcup_{i\in I}A_i\).
The types \(t_0,t_j\) follow the same path. Indeed, inductively, whenever they have reached the same node:
The policy therefore selects the same terminal decision for these two types. Whichever decision it selects, one of them receives reward \(0\). Its mass is at least \(1/B\).
The undiscounted terminal reward is thus at most \(1-1/B\). Discounting cannot increase nonnegative terminal rewards, and costs cannot increase value. Hence
\(V(\pi)\leq1-1/B<\eta.\)
This contradiction proves the equivalence
\(\text{there is a set cover of size at most }k\quad\Longleftrightarrow\quad\exists\pi:\ V(\pi)\geq\eta.\)
The reduction has \(m=M+2,\ \tau=N+1,\ |D|=2,\ H=k\). Its utility table has polynomial size; \(\log B\) and \(\log C\) are logarithmic in the source parameters; and \(\eta=(C-1)^k/C^k\) uses \(O(k\log C)\) bits. Since \(k\leq M\), writing \(H\) in unary and writing \(\eta\) explicitly both take polynomial time. This completes the \(\mathrm{NP}\)-hardness proof.
5. Finite query representatives and an exact algorithm. For completeness, the continuous threshold parameter can be eliminated exactly.
For outcome \(s_i\), list its distinct support utilities as
\(v_{i,1}<\cdots<v_{i,r_i},\qquad r_i\leq\tau.\)
The response probabilities depend only on the set of types satisfying \(u_t(s_i)<l\). Representatives for all possible such sets are:
To verify completeness, thresholds at most \(v_{i,1}\) give the empty set; thresholds in \((v_{i,j},v_{i,j+1}]\) give the same set as \(v_{i,j+1}\); and thresholds above the maximum, when possible, give the same set as \(1\). The endpoint convention follows from the strict inequality \(u_t(s_i)<l\).
There are therefore at most \(K=m(\tau+1)\) representative queries. Replacing every query by its representative preserves its response probabilities and cost, hence preserves the entire policy value.
For a nonnegative mass vector \(x\), let \(F_h(x)\) be the maximum value measured from the current node with at most \(h\) further queries. Define
\(A(x)=\max_{d\in D}\sum_t x_tR(d,t).\)
For representative query \(q\), write \(\rho_{q,r,t}=P(r\mid q,t)\) and \(x^{q,r}_t=x_t\rho_{q,r,t}\). Then
\(F_0(x)=A(x),\)
and, for \(h\geq1\),
\(F_h(x)=\max\left\{A(x),\ \max_q\left[-c_q\sum_t x_t+\gamma\bigl(F_{h-1}(x^{q,\mathrm{yes}})+F_{h-1}(x^{q,\mathrm{no}})\bigr)\right]\right\}.\)
This recurrence is exact: a policy either terminates immediately or asks one query, after which its two continuation policies can be chosen independently. Induction on \(h\) proves both the upper bound and attainability. The answer is obtained by comparing \(F_H(\mu)\) with \(\eta\).
Precomputing rewards takes \(O(|D|m\tau)\) rational arithmetic operations. Depth-first evaluation of the recurrence gives the bit-time bound
\(O\!\left(\left[|D|m\tau+\bigl(2m(\tau+1)\bigr)^H\bigl(m(\tau+1)+|D|\bigr)\tau\right]\operatorname{poly}(H,L)\right).\)
Thus every fixed-horizon case is polynomial-time solvable.
To justify exact arithmetic, let \(Q\) be the product of all input denominators, so \(\log Q=O(L)\). A mass coordinate at depth \(d\) has denominator dividing \(Q^{d+1}\). A terminal contribution after another \(r\) queries has denominator dividing \(Q^{d+2r+3}\); a cost contribution has denominator dividing \(Q^{d+2r+2}\). Since \(d+r\leq H\), all these denominators divide \(Q^{2H+3}\). Summation and maximization preserve this common denominator bound.
The absolute value of any policy value is at most \(1+Hc_{\max}\). Consequently, all exact values need only \(O((H+1)L+\log(H+1))\) bits. A depth-first implementation stores only polynomially many such numbers along a recursion stack of depth \(H\). Because \(H\) is unary, this proves membership in \(\mathrm{PSPACE}\).
6. Deterministic responses give \(\mathrm{NP}\)-completeness. When every response probability is in \(\{0,1\}\), each of the \(\tau\) types follows one path of length at most \(H\). The union of these paths contains at most \(1+\tau H\) nodes. Unreachable branches can be filled with arbitrary terminal decisions without changing value.
A certificate can therefore specify a polynomial-size policy tree using representative query indices and decision indices. A verifier simulates each type’s path and evaluates exactly
\(\sum_t\mu_t\left[\gamma^{\ell_t}R(d_t,t)-\sum_{j=0}^{\ell_t-1}\gamma^j c_{i_{t,j}}\right].\)
After reward precomputation, this takes \(O(\tau H)\operatorname{poly}(H,L)\) time. The deterministic-response restriction belongs to \(\mathrm{NP}\); Sections 1–4 establish its \(\mathrm{NP}\)-hardness.
The requested classification is therefore resolved: the stated mass problem is \(\mathrm{NP}\)-hard, and a polynomial-time algorithm for unrestricted inputs would imply \(\mathrm P=\mathrm{NP}\).
⟨structured verdict parsed — rendered above⟩
The claimed hardness classification is correct. The reduction establishes \(\mathrm{NP}\)-hardness for the exact terminal-reward model in USER_TASK. The additional \(\mathrm{NP}\)-completeness and \(\mathrm{PSPACE}\)-membership arguments are sound. I found one minor issue: the certificate-verification running-time bound omits the allowed case \(H=0\).
The constructed instance satisfies the task’s requirements.
Deleting duplicate incidence vectors preserves Set Cover feasibility. The outcomes \(z,w\) distinguish \(t_0\) from every element type, so this preprocessing also supports the assertion that the constructed types are distinct.
The attribution to the distinguished-state construction is accurate: [Conitzer and Sandholm, Theorem 3](https://www.cs.cmu.edu/~conitzer/metareasoningIJCAI03.pdf) uses a distinguished state and queries corresponding to sets. The present argument independently verifies its different terminal rewards; it does not assume that the cited identification reward is available here.
With \(a_i=b_i=0\), the stipulated response rule gives yes exactly when \(u_t(s_i)\geq l\).
Consequently:
These statements correctly include the equality convention at both endpoints.
Bernoulli’s inequality applies because \(k\) is a positive integer and \(-1/C>-1\). The displayed separation is valid: \(C\geq4B(k+1)\) implies \(k/C<1/(4B)\), hence \(\eta>1-1/B\). Since \(B\geq2\), the additional assertion \(\eta>1/2\) is also valid.
This argument is correct.
Under deterministic responses, each type either reaches a node with its entire original mass or does not reach it. Every reachable node therefore has mass at least \(1/B\).
A queried node has depth at most \(k-1\), so the weaker bound \(\gamma^d\geq\gamma^k\) used in the output holds. A query about \(z\) or \(w\) thus incurs discounted cost at least \(2\eta>1\).
Total discounted terminal reward is at most \(1\): each type terminates once, its reward is at most \(1\), and discounting cannot increase that reward. Other costs are nonnegative. The resulting negative-value bound is valid, including when the expensive query uses an uninformative threshold.
Thus no qualifying policy can use either expensive query at a reachable node.
Cover implies qualifying policy. The proposed policy correctly classifies every type. Every element type encounters a yes response by the end of the selected cover; \(t_0\) encounters only no responses. All costs are zero, and every terminal depth is at most \(k\). Therefore the displayed lower bound \(V(\pi)\geq\gamma^k=\eta\) follows.
Qualifying policy implies cover. The argument correctly handles adaptive policies by examining the actual path of \(t_0\).
There are at most \(k\) positive-threshold membership queries on that path. If their sets do not cover the universe, an uncovered element type gives exactly the same responses as \(t_0\), including yes responses to threshold-zero queries. Determinism of the policy then forces the same terminal decision for both types.
Either decision misclassifies one of these types, whose mass is at least \(1/B\). Thus undiscounted terminal reward is at most \(1-1/B\). Nonnegative rewards, discounting, and nonnegative costs justify \(V(\pi)\leq1-1/B<\eta\).
The equivalence is established without assuming certain identification or allowing actions to depend on type.
The size accounting is correct.
The utility table has polynomial size, and the stated bounds on \(\log B,\log C\) hold. Writing \(\eta=(C-1)^k/C^k\) requires \(O(k\log C)\) bits. Its exact computation and the unary encoding of \(H=k\) take polynomial time.
The reduction therefore establishes the claimed polynomial-time many-one \(\mathrm{NP}\)-hardness, including the restrictions to deterministic responses, binary utilities, and two decisions.
The representative list is complete.
Thresholds at most the minimum support utility produce the empty strict-lower set, represented by \(0\). Each interval \((v_{i,j},v_{i,j+1}]\) is represented by \(v_{i,j+1}\). Thresholds above the maximum exist precisely when that maximum is below \(1\), and are represented by \(1\).
This covers singleton utility lists and utilities equal to \(0\) or \(1\). The bound \(K\leq m(\tau+1)\) is valid.
The recurrence correctly uses unnormalized masses. Costs are charged to the current node’s entire mass, and the discount multiplies both continuation values. Independent continuation choices are permitted because histories distinguish the branches, while no action depends on the hidden type.
The base case \(F_0(x)=A(x)\), induction, and attainability argument are sufficient.
The general algorithm’s stated running-time bound is valid, though loose. Depth-first evaluation has the claimed exponential dependence on \(H\), and fixed \(H\) gives polynomial time in the remaining input parameters.
The denominator bounds are valid conservative bounds. Response probabilities have denominators dividing \(Q\); terminal rewards have denominators dividing \(Q^2\). The stated powers account for accumulated response factors and discounts. A common denominator dividing \(Q^{2H+3}\) suffices.
For masses reachable from the initial society, total mass is at most \(1\). Consequently, the bound \(1+Hc_{\max}\) on absolute policy values and the resulting polynomial bit lengths are valid. Depth-first evaluation stores polynomially many polynomial-length numbers because \(H\) is unary. The \(\mathrm{PSPACE}\) conclusion follows.
Each type follows one path, so the union of reachable paths contains at most \(1+\tau H\) nodes. Adding terminal decisions on unreachable branches preserves polynomial certificate size.
The displayed per-type evaluation formula agrees with the original node-based value: deterministic responses assign each queried cost to precisely the types reaching that node. Representative query indices and decision indices have polynomial encodings.
Minor issue: The post-precomputation bound \(O(\tau H)\operatorname{poly}(H,L)\) does not cover \(H=0\). At that horizon, the verifier must still evaluate the terminal decision’s weighted reward and compare it with \(\eta\).
Minimum clarification requested: State the verification bound with an additive base-case term, or give the \(H=0\) running time separately. This requires no new mathematical argument and does not affect membership in \(\mathrm{NP}\).
No major issue or missing lemma blocks the 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.