Answer: Polynomial-time solvable for unrestricted executable descriptions with uncharged execution time; \(\mathrm{NP}\)-hard when the initial action must be extractable in polynomial time.
Theorem 1 — class: other
PDF text-layer excerpt — equations and symbol order may be approximateIf, for every state permutation πs(s) and action a, there exists an action aπs and observation permutation ππs,a(o) such that • R(s, a) = R(πs(s), aπs) • Ω(o|s, a) = Ω(ππs,a(o)|πs(s), aπs) • T(s′|s, a) = T(πs(s′)|πs(s), aπs), then for every vector α in the value function, all permutations of α are also part of the value function.2 PROOF. Recall that for the exact POMDP solution, the value function is the union over actions of the α vectors in Γa.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite set of user-goal types \(G\), rational population masses \(\mu_g\) summing to one, a finite discounted POMDP for each session, and \(\epsilon>0\), find a common policy mapping each session's dialog history to queries, confirmations, or a submission whose expected discounted reward per user is within \(\epsilon\) of the maximum.
Let \(S\) be a finite set of \(m\) possible user goals. A society is given by its support \(G\subseteq S\): the list of its \(\tau\) types with positive binary-rational masses \(\mu_g\), summing to one; \(\tau\) is the support size, not the number of possible types.
Every user session uses the same explicitly tabulated finite POMDP \((S,A,O,T,\Omega,R,\gamma)\), initially distributed according to \(\mu\). The sets \(S,A,O\) are nonempty; transition and observation probabilities are rational, rewards are signed rationals, and \(0\leq\gamma<1\).
Actions are queries, confirmations, or submissions, with their effects and rewards specified by the tables. Submissions need not terminate interaction. Observations follow transitions: \(\Omega(o\mid s',a)\) is conditioned on the resulting state.
Promise full permutation symmetry: for every permutation \(\sigma\) of \(S\) and every \(a\in A\), there exist \(a_\sigma\in A\) and a permutation \(\rho_{\sigma,a}\) of \(O\) such that, for all \(s,s',o\),
\(R(s,a)=R(\sigma(s),a_\sigma),\quad T(s'\mid s,a)=T(\sigma(s')\mid\sigma(s),a_\sigma),\quad\Omega(o\mid s,a)=\Omega(\rho_{\sigma,a}(o)\mid\sigma(s),a_\sigma).\)
A common deterministic policy uses only the current session's action-observation history, with no observation of its hidden goal or access to other sessions. Its per-user value is \(J_\mu(\pi)=\sum_{g\in G}\mu_g\mathbb E_g^\pi[\sum_{t=0}^{\infty}\gamma^tR(s_t,a_t)]\).
Given binary-rational \(\epsilon>0\), the computational problem is to produce a finite executable description of such a policy with \(J_\mu(\pi)\geq\sup_{\pi'}J_\mu(\pi')-\epsilon\). Let \(L\) be the total binary input length, including the model, masses, discount, and accuracy.
Is this policy-synthesis problem solvable in time polynomial in \(m,\tau,|A|,|O|,L\), or is it NP-hard?
The finite-model symmetry result establishes closure of the value-function vectors under state permutations; it gives no polynomial-time complexity classification. [Symmetry result](https://groups.csail.mit.edu/rrg/papers/aamas08-fd.pdf)
For general POMDPs, point-based value iteration has approximation-error bounds depending on belief-space sampling density. No complexity classification for the precise promised mass problem was located. [Point-based approximation](https://robots.stanford.edu/papers/Pineau03a.pdf)
1. Result and output convention
Under the intended operational interpretation—where the initial action can be extracted from the synthesized description in polynomial time—the problem is \(\mathrm{NP}\)-hard. This holds even with \(m=\tau=7\), one observation, a fixed initial distribution, and \(\gamma=1/2\).
There is one qualification in the wording: unrestricted executable programs can postpone all planning until execution. If those are admissible descriptions and execution time is uncharged, polynomial-time synthesis is possible. I prove the substantive hardness result first, then establish this literal alternative.
The representation assumption needed for hardness is only:
There is a uniform polynomial-time procedure that extracts the policy’s initial action from its description.
Explicit policy trees and finite controllers satisfy this assumption.
2. An \(\mathrm{NP}\)-hard integer-sum problem
We first establish hardness of the following problem: given positive integers \(w_1,\ldots,w_d\), a positive integer \(B\), and a polynomially bounded integer \(N\), decide whether exactly \(N\) members of the list, with repetitions permitted, sum to \(B\).
Reduce from positive-integer SUBSET SUM, whose \(\mathrm{NP}\)-completeness is classical. [Karp’s original paper](https://www.cs.umd.edu/~gasarch/BLOGPAPERS/Karp.pdf)
Given \(a_0,\ldots,a_{N-1}\) and target \(B_0\), put \(q=N+1\), and introduce the \(2N\) weights
\(w_i^0=q^i,\qquad w_i^1=q^i+a_iq^N,\qquad 0\leq i<N.\)
Set the new target to
\(B=\sum_{i=0}^{N-1}q^i+B_0q^N.\)
Consider a sum of exactly \(N\) new weights. If \(n_i\) counts the weights selected from the pair indexed by \(i\), then \(0\leq n_i\leq N<q\). Consequently, there are no carries among the lowest \(N\) base-\(q\) digits. Equality with the target forces \(n_i=1\) for every \(i\). The remaining equality is precisely that the original numbers whose \(w_i^1\) versions were selected sum to \(B_0\).
Conversely, any original subset summing to \(B_0\) gives such an \(N\)-term sum by selecting one version of every pair. All constructed numbers have polynomial binary length.
Hence this integer-sum problem is \(\mathrm{NP}\)-hard even when \(d=2N\).
3. Encoding integer arithmetic in seven-state beliefs
Throughout the construction, beliefs are column vectors, and transition matrices are column stochastic.
Define the fixed vectors
\(p=\frac1{32}(1,2,3,4,5,6,11)^\top,\qquad r=(1,2,3,4,5,6,7)^\top.\)
Thus \(\mathbf 1^\top p=1\), and
\(C=r^\top p=\frac{21}{4}.\)
Let \(u_1,\ldots,u_7\) be the standard basis of \(\mathbb R^7\). Define a \(7\)-by-\(5\) matrix \(E\) by its columns:
\(E_j=u_j+(j-7)u_6+(6-j)u_7,\qquad 1\leq j\leq5.\)
Define the linear map \(F:\mathbb R^7\to\mathbb R^5\) by
\((Fb)_j=b_j-p_j\mathbf 1^\top b,\qquad 1\leq j\leq5.\)
Direct calculation gives
\(\mathbf 1^\top E=0,\qquad r^\top E=0,\qquad FE=I_5,\qquad Fp=0.\)
For example, the sum of the entries of \(E_j\) is \(1+(j-7)+(6-j)=0\), and
\(r^\top E_j=j+6(j-7)+7(6-j)=0.\)
Because the first five rows of \(E\) form the identity matrix, the other two identities follow immediately.
For each weight \(w\), define the linear map \(M_w:\mathbb R^5\to\mathbb R^5\) by
\(M_w(z,k,u,x,v)^\top=(z,\ k+z,\ u+2k+z,\ x+wz,\ v+2wx+w^2z)^\top.\)
Writing
\(v(k,x)=(1,k,k^2,x,x^2)^\top,\)
we obtain the exact identity
\(M_wv(k,x)=v(k+1,x+w).\)
Thus these maps maintain a count, an accumulated sum, and their squares.
Put
\(D_w=EM_wF,\qquad K=\max\{1,\lvert(D_w)_{ij}\rvert:w\text{ is a listed weight},\ 1\leq i,j\leq7\}.\)
Let \(h=2^{-12}\). Choose a positive dyadic rational \(c\) satisfying
\(c\leq\frac14,\qquad 7cK\leq h.\)
For each weight, introduce a computational action with transition matrix
\(P_w=p\mathbf 1^\top+cD_w\)
and reward vector \(r\).
These are valid transition matrices. Indeed, \(\mathbf 1^\top D_w=0\), so every column sums to one. Also,
\((P_w)_{ij}\geq p_i-cK\geq\frac1{32}-\frac h7>0.\)
For every probability vector \(b\),
\(P_wb=p+cD_wb,\qquad \|P_wb-p\|_1\leq7cK\leq h,\)
and
\(r^\top(P_wb-p)=0.\)
Set \(\delta=2^{-20}\), and use the fixed initial distribution
\(\mu=p+\delta Ev(0,0).\)
Its entries are positive dyadic rationals and sum to one. Moreover,
\(\|\mu-p\|_1=12\delta<h,\qquad r^\top(\mu-p)=0.\)
After \(k\) computational actions whose weights sum to \(x\), the belief is exactly
\(b_k=p+\delta c^kEv(k,x).\)
This follows inductively from \(Fp=0\), \(FE=I_5\), and the identity for \(M_w\).
4. Two submission actions
Set \(\gamma=1/2\) and \(\lambda=\gamma c\), so \(0<\lambda\leq1/8\).
Define
\(\alpha=(1/2-N^2-B^2,\ 2N,\ -1,\ 2B,\ -1)^\top.\)
Then
\(\alpha^\top v(k,x)=\frac12-(k-N)^2-(x-B)^2.\)
Let
\(\ell=F^\top\alpha,\qquad f=F^\top(1,0,0,0,0)^\top,\)
and put
\(K_R=\max\{1,\|\ell\|_\infty,\|f\|_\infty\},\qquad \Delta=\frac1{32}.\)
Choose a positive dyadic rational \(\eta\leq1\) satisfying
\(\frac{\eta K_R}{1-\gamma}\leq\frac{\Delta}{8}.\)
Introduce two submission actions, both with transition matrix \(p\mathbf 1^\top\):
These submissions reset the belief to \(p\); they do not terminate interaction.
At \(b_k\), the expected reward above the common baseline \(C\) is respectively
\(\eta\delta c^k\left[\frac12-(k-N)^2-(x-B)^2\right]\)
and
\(\eta\delta c^k\theta.\)
After either submission, \(Fb=Fp=0\). Computational actions preserve \(p\), so subsequent actions of this orientation produce only the baseline reward.
5. Full permutation symmetry—and why extra actions do not help
For every action just constructed and every permutation \(\sigma\) of the seven states, explicitly include an action obtained by conjugating its transition matrix and permuting its reward vector.
If \(U_\sigma\) is the permutation matrix, these tables are
\(P_{a,\sigma}=U_\sigma P_aU_\sigma^{-1},\qquad R_{a,\sigma}=U_\sigma R_a.\)
Use a singleton observation set, with observation probability one under every state and action.
This model satisfies the promised symmetry exactly: a further state permutation \(\kappa\) maps action \((a,\sigma)\) to \((a,\kappa\sigma)\), and the observation permutation is the identity. There are only \(7!\) copies of each base action.
We must prove that the added copies do not invalidate the encoding.
Write \(p_\sigma=U_\sigma p\) and \(r_\sigma=U_\sigma r\). After any action of orientation \(\sigma\), its resulting belief satisfies
\(\|b-p_\sigma\|_1\leq h,\qquad r_\sigma^\top(b-p_\sigma)=0.\)
For computational actions this follows from the bounds above after conjugation; for submissions the resulting belief is exactly \(p_\sigma\). The initial belief has these properties for the identity orientation.
Suppose the current belief has these properties for orientation \(\theta\). An action of orientation \(\theta\) has baseline expected reward exactly \(C\).
For \(\sigma\ne\theta\), the strict rearrangement inequality gives
\(r_\sigma^\top p_\theta<C.\)
Here all coordinates of \(p\) are distinct and increasing, as are those of \(r\), so their matching order uniquely maximizes their scalar product. Furthermore, all such scalar products are multiples of \(1/32\). Therefore,
\(r_\sigma^\top p_\theta\leq C-\Delta.\)
It follows that an action of a different orientation has baseline expected reward at most
\(r_\sigma^\top b\leq C-\Delta+7h\leq C-\frac{3\Delta}{4}.\)
Thus every action has baseline expected reward at most \(C\), while an orientation mismatch loses at least \(3\Delta/4\) immediately.
The absolute additional reward from either submission is at most \(\eta K_R\). Hence the total possible discounted additional reward from any time onward is at most
\(\frac{\eta K_R}{1-\gamma}\leq\frac{\Delta}{8}.\)
Consequently, a continuation beginning with an orientation mismatch has value at most
\(\frac{C}{1-\gamma}-\frac{3\Delta}{4}+\frac{\Delta}{8} =\frac{C}{1-\gamma}-\frac{5\Delta}{8}.\)
By contrast, repeatedly taking a computational action of the current orientation earns exactly \(C\) at every subsequent step, giving \(C/(1-\gamma)\).
Therefore any policy containing an orientation mismatch is strictly improved by replacing its suffix from the first mismatch onward with this baseline continuation.
There is only one observation, so each deterministic policy induces a fixed action sequence. Every sequence with a mismatch has a first mismatch. It follows that the optimal value equals the supremum over sequences that always retain the initial, identity orientation.
This establishes the essential point: full permutation closure introduces no profitable shortcut.
6. Exact values and a forced initial-action gap
Let
\(V_{\mathrm{base}}=\frac{C}{1-\gamma},\qquad Q=\frac{\eta\delta\lambda^N}{4},\qquad \epsilon=\frac Q4.\)
Consider an identity-oriented sequence. If its first submission occurs after \(k\) computational actions, their accumulated weight is an integer \(x\).
The discounted additional value of a test submission is
\(\eta\delta\lambda^k\left[\frac12-(k-N)^2-(x-B)^2\right].\)
Since \(k,N,x,B\) are integers, this is positive exactly when \(k=N\) and \(x=B\). In that case it equals
\(\frac{\eta\delta\lambda^N}{2}=2Q.\)
In every other case, the bracket is at most \(-1/2\).
A safe submission after \(k\) computations contributes
\(Q\lambda^k\leq Q,\)
with equality at \(k=0\). A sequence with no submission has value \(V_{\mathrm{base}}\). After the first submission, identity-oriented actions produce no further additional reward.
Together with the domination argument, this proves the exact formula
\(V^*(\mu)=
\begin{cases}
V_{\mathrm{base}}+2Q,&\text{if an $N\)-term sum equals \(B\)},\\
V_{\mathrm{base}}+Q,&\text{otherwise}.
\end{cases}\)
Now consider the initial action of an \(\epsilon\)-optimal policy.
In a no-instance:
The computational-action gap is at least
\((1-\lambda)Q\geq\frac{7Q}{8}>\epsilon.\)
Hence every \(\epsilon\)-optimal policy must initially choose the identity-oriented safe action.
In a yes-instance, that safe action gives only \(V_{\mathrm{base}}+Q\), which is \(Q>\epsilon\) below optimum. The test action and different orientations are also excluded by their bounds. Hence every \(\epsilon\)-optimal policy must initially choose an identity-oriented computational action.
Therefore,
\(\text{the integer-sum instance is a no-instance} \quad\Longleftrightarrow\quad \pi(\varnothing)\text{ is the identity-oriented safe action}\)
for every valid synthesis output.
Extracting just the initial action decides the original \(\mathrm{NP}\)-hard problem.
7. Encoding length and the operational hardness conclusion
All quantities have polynomial binary length:
The constructed instance has
\(m=\tau=7,\qquad |O|=1,\qquad |A|=7!(d+2),\qquad \gamma=1/2,\)
and fixed positive dyadic initial masses.
Thus, under any representation permitting polynomial-time initial-action extraction, polynomial-time synthesis in the parameters requested would imply \(\mathrm P=\mathrm{NP}\).
This is a complete hardness proof for that operational interpretation. It uses the binary encoding of accuracy; it does not establish hardness for fixed accuracy and uniformly bounded numerical precision.
8. Unrestricted executable descriptions: polynomial-time compilation
For completeness, suppose arbitrary terminating policy programs are allowed, without a bound on their execution time.
There is then a synthesis algorithm that outputs a fixed planning program containing the input instance as embedded data. Copying that data and fixed code takes polynomial time.
Here is why the resulting program specifies a valid policy. Let
\(M=\max_{s,a}|R(s,a)|.\)
When \(M=0\), any fixed action suffices. Otherwise, the program computes a finite horizon \(H\geq1\) satisfying
\(\frac{2M\gamma^H}{1-\gamma}\leq\epsilon.\)
Such an \(H\) exists since \(\gamma<1\). It enumerates all deterministic depth-\(H\) policy trees, evaluates their finite-horizon values exactly using the rational tables, and selects a maximizing tree using a fixed tie-breaking rule. It follows that tree for \(H\) steps and thereafter always takes a fixed action.
Every policy has discounted tail bounded in absolute value by
\(B_H=\frac{M\gamma^H}{1-\gamma}.\)
If \(V_H^*\) is the optimal truncated value and \(\widehat\pi\) is the program’s policy, then
\(\sup_\pi J_\mu(\pi)\leq V_H^*+B_H,\qquad J_\mu(\widehat\pi)\geq V_H^*-B_H.\)
Therefore,
\(J_\mu(\widehat\pi)\geq\sup_\pi J_\mu(\pi)-2B_H \geq\sup_\pi J_\mu(\pi)-\epsilon.\)
The enumeration is finite, so execution terminates. The program uses only its embedded instance and the current session’s history. Its potentially enormous execution time does not affect the compilation time.
Accordingly, the unrestricted-program reading is polynomial-time solvable; the intended operational synthesis problem is \(\mathrm{NP}\)-hard, even under the strong restrictions proved above.
⟨structured verdict parsed — rendered above⟩
Verdict: the representation-dependent conclusion is proved. The reduction establishes \(\mathrm{NP}\)-hardness when a policy’s initial action can be extracted in polynomial time. The compilation argument establishes polynomial-time synthesis when arbitrary executable descriptions are permitted and execution time is uncharged. I found no mathematical error or blocking gap.
The word “intended” does not establish that polynomial-time action extraction is required by USER_TASK. The output appropriately makes that assumption explicit and separately addresses unrestricted programs.
1. Integer-sum reduction
The source problem is binary-encoded SUBSET SUM with positive integer weights and a positive target. Its hardness is standard; the positive-integer formulation is also explicitly described in [Subset Sum Made Simple](https://arxiv.org/abs/1807.08248).
The reduction correctly enforces exactly one choice from each pair:
The converse is valid, repetitions do not undermine the construction, and the constructed integers have polynomial binary length. The hardness claim applies to nonempty source instances, so the later use of \(N\geq1\) is justified.
2. Seven-state belief encoding
The numerical and linear-algebra identities are correct:
\[ \mathbf 1^\top p=1,\qquad r^\top p=\frac{91+77}{32}=\frac{21}{4}. \]
For every column \(E_j\), its coordinate sum and its scalar product with \(r\) vanish. Since its first five coordinates form the corresponding standard basis vector, the definitions give \(FE=I_5\). The identity \(Fp=0\) follows from normalization of \(p\).
The arithmetic map correctly updates both squares:
\[ k^2+2k+1=(k+1)^2,\qquad x^2+2wx+w^2=(x+w)^2. \]
Consequently, the stated identity for \(M_wv(k,x)\) holds.
The transition validity checks also hold. Column sums equal one because \(\mathbf 1^\top D_w=0\), and the lower bound on every entry is strictly positive. For a probability vector, the entrywise bound on \(D_w\) gives the claimed \(7cK\) bound in the norm \(\|\cdot\|_1\). Orthogonality to \(r\) follows from \(r^\top E=0\).
The initial distribution is normalized and strictly positive. Since \(Ev(0,0)=E_1\), its stated deviation satisfies
\[ \|\mu-p\|_1=12\delta<h. \]
The belief recurrence follows from the identities already established. It preserves the encoded count, sum, and squares exactly. No assumption that the accumulated sum remains numerically small is needed: transition validity was proved for every probability vector.
3. Submission rewards
The quadratic expression is correct:
\[ \alpha^\top v(k,x)=\frac12-(k-N)^2-(x-B)^2. \]
The definitions of \(\ell\) and \(f\), together with \(Fp=0\) and \(FE=I_5\), give exactly the stated additional rewards at \(b_k\).
Both submissions reset the belief to \(p\). Subsequent actions in the same orientation preserve \(p\), and both additional reward vectors have zero expectation there. Thus only the first submission can contribute additional value along an identity-oriented sequence.
The numerical bound on additional rewards is valid for the safe action as well as the test action: \(0<\theta\leq1\).
4. Permutation symmetry
The conjugated transition matrices and permuted reward vectors satisfy the promised transition and reward identities. Singleton observations satisfy the observation identity, including the task’s convention that observations follow transitions.
Composition sends the action indexed by \(\sigma\) to the action indexed by \(\kappa\sigma\), as claimed. Explicit closure adds only the constant factor \(7!\).
The post-action proximity and orthogonality invariants remain valid under conjugation. They apply regardless of the incoming belief, which is essential for analyzing arbitrary switches of orientation.
5. Excluding orientation switches
The rearrangement argument has the required hypotheses: both \(p\) and \(r\) have strictly increasing, distinct coordinates. Matching their orders is the unique maximizing permutation. Distinct orientations therefore give a strictly smaller scalar product.
Every such product is a multiple of \(1/32\), so the loss is at least \(\Delta=1/32\). The perturbation estimate is valid because \(\|r_\sigma\|_\infty=7\). The numerical comparison also holds:
\[ 7h=\frac7{4096}<\frac1{128}=\frac{\Delta}{4}. \]
Thus an orientation mismatch loses at least \(3\Delta/4\) in baseline reward.
The discounted bound \(\Delta/8\) includes all future additional rewards, including rewards after further orientation changes. Combining it with the baseline bound proves the claimed strict disadvantage.
Replacing the suffix from the first mismatch preserves every earlier reward. Since \(\gamma=1/2>0\), the strict continuation improvement gives a strict improvement in initial value. Singleton observations ensure that a deterministic policy induces a fixed sequence, so every sequence containing a mismatch has a first one. The reduction to identity-oriented sequences is justified.
6. Optimal values and initial-action separation
The discount factor is correctly combined with the belief attenuation through \(\lambda=\gamma c\).
Because \(k,N,x,B\) are integers, the test reward is positive exactly at \(k=N\) and \(x=B\). At every other pair, its bracket is at most \(-1/2\). The successful discounted bonus is \(2Q\).
The safe bonus is \(Q\lambda^k\), maximized by immediate submission. Sequences without submissions have exactly the baseline value. These observations, together with orientation domination, establish both branches of the stated optimal-value formula.
The initial-action separation is valid:
Therefore every valid approximate synthesis output has the asserted initial-action classification. Polynomial-time extraction of that action would decide the source problem in polynomial time.
7. Encoding and complexity
The encoding claims are sound. Squaring a binary-encoded weight increases its bit length only linearly. The fixed matrices introduce no growing dimension. Suitable dyadic scales can be selected with denominator bit lengths polynomial in the source input length.
Since \(N\) is polynomially bounded, the binary lengths of the powers defining \(\theta,Q,\epsilon\) remain polynomial. The fixed initial distribution has all seven masses positive, so \(m=\tau=7\) respects the task’s definition of support size.
The conclusion is appropriately limited to binary-encoded accuracy. The argument does not claim fixed-accuracy hardness.
8. Unrestricted executable descriptions
The compilation argument also stands.
For \(M=0\), every policy has value zero. Otherwise, the required finite horizon exists for every permitted discount. The edge case \(\gamma=0\) is covered by any \(H\geq1\).
There are finitely many deterministic depth-\(H\) policy trees. Their truncated values are exactly computable from the rational model, initial masses, and discount. Enumeration and fixed tie-breaking therefore terminate and define a deterministic policy.
The two tail inequalities correctly account for signed rewards. They establish the desired approximation without assuming that the infinite-horizon supremum is attained.
Embedding the input and fixed planning code requires polynomial synthesis time and description length. The program uses only the embedded model and the current session’s history. Its potentially enormous execution time is admissible under the explicitly stated unrestricted-program convention.
Required clarification
No mathematical repair is required. To obtain a single unconditional complexity classification, specify whether admissible policy descriptions must permit polynomial-time initial-action extraction. The supplied output already explains the consequences of both conventions.
⟨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.