Answer: \(\mathrm{NP}\text{-hard}\), even with one worker type and fixed positive regularization and accuracy parameters.
Theorem 1 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateAssume β is strictly positive. Then Algorithm 1 produces a sequences Λ(1), Λ(2), . . . such that lim ℓ→∞Lβ ˜π(Λ(ℓ)) = min Λ Lβ ˜π(Λ). Let ˆΛ be the solution of Algorithm 1. We next show that if we generate enough samples m, the loss of the estimate ˆΛ under the true posterior will not be much higher than that obtained by any distribution of the form (1).
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given \(N\) concepts, worker response types \(r\) with rational population masses \(\mu_r\), and per-type answer frequencies \(v_{r,q,a}\) for path query \(q\) and answer \(a\), form \(Q_\mu(T)\propto \pi_0(T)\exp(\sum_{r,q,a}\mu_r v_{r,q,a}\log f_r(a\mid T,q))\) over rooted hierarchies \(T\). For \(P_\Lambda(T)=\exp(\sum_{e\in T}\lambda_e)/Z(\Lambda)\), find \(\Lambda\) within \(\epsilon\) of the minimum of \(\mathbb{E}_{T\sim Q_\mu}[-\log P_\Lambda(T)]+\beta\sum_e|\lambda_e|\); determine the convergence and finite-precision complexity in \(N\), support size \(\tau\), input bit length \(L\), and \(\epsilon^{-1}\).
Let \(m=N\geq1\) be the number of concepts, with an additional fixed root \(0\). Set \(E=\{(i,j):0\leq i\leq N,\ 1\leq j\leq N,\ i\neq j\}\); let \(\mathcal T\) contain all spanning arborescences directed away from \(0\), and let \(\pi_0\) be uniform on \(\mathcal T\).
A society is given by its support: a list of \(\tau\) worker types with positive binary-rational masses \(\mu_r\), summing to \(1\). Here \(\tau\) is the support size, not the number of possible types.
Each type specifies a binary-rational error rate \(0<\gamma_r<1\) and nonnegative binary-rational answer frequencies \(v_{r,q,a}\), interpreted as expected answer counts per worker, without normalization. Queries \(q=(i,j)\) concern distinct concepts, answers satisfy \(a\in\{0,1\}\), and omitted frequencies are zero.
Write \(h_q(T)=1\) precisely when \(T\) contains a directed path from \(i\) to \(j\). Define \(f_r(a\mid T,q)=1-\gamma_r\) if \(a=h_q(T)\), and \(f_r(a\mid T,q)=\gamma_r\) otherwise.
Define \(Q_\mu(T)=C^{-1}\pi_0(T)\exp(\sum_{r,q,a}\mu_r v_{r,q,a}\log f_r(a\mid T,q))\), where \(C\) normalizes the distribution. The input supplies these parameters, without a posterior sampling or marginal oracle.
For \(\Lambda\in\mathbb R^E\), set \(P_\Lambda(T)=\exp(\sum_{e\in T}\lambda_e)/Z(\Lambda)\), with \(Z(\Lambda)=\sum_{T\in\mathcal T}\exp(\sum_{e\in T}\lambda_e)\). Given binary-rational \(\beta>0\) and \(0<\epsilon<1\), define \(F(\Lambda)=\mathbb E_{Q_\mu}[-\log P_\Lambda(T)]+\beta\sum_{e\in E}|\lambda_e|\).
The computational problem is to find a rational \(\widehat\Lambda\) satisfying \(F(\widehat\Lambda)\leq\min_{\Lambda\in\mathbb R^E}F(\Lambda)+\epsilon\). Let \(L\) be the total input bit length.
Does this problem admit a deterministic algorithm with finite-precision running time polynomial in \(m=N\), \(\tau\), \(L\), and \(\epsilon^{-1}\), or is it NP-hard?
For an explicitly supplied empirical distribution over trees and \(\beta>0\), iterative minimization of a separable upper bound is known to converge in objective value to the global minimum; no finite-precision polynomial-time bound is established by that result. [Source](https://arxiv.org/pdf/1504.07302)
No result settling the complexity of the implicitly specified mass-posterior problem above was located.
The problem is \(\mathrm{NP}\)-hard, even when \(\tau=1\), \(\mu_1=1\), \(\gamma_1=1/4\), \(\beta=1/64\), and \(\epsilon=1/8192\).
More precisely, one call to an algorithm returning any valid approximate minimizer, followed by polynomial-time finite-precision computation, suffices to solve an \(\mathrm{NP}\)-complete decision problem. Thus the requested deterministic polynomial-time algorithm would imply \(\mathrm{P}=\mathrm{NP}\).
The proof uses the permitted, unnormalized answer frequencies. Some frequencies have exponentially large values, but their binary encodings have polynomial length.
We reduce from directed Feedback Arc Set: given a loopless directed graph \(G=([n],A)\) and an integer \(k\), decide whether deleting at most \(k\) arcs makes the graph acyclic. This problem is \(\mathrm{NP}\)-complete; Karp’s reduction produces loopless graphs without parallel arcs. [Karp, *Reducibility among Combinatorial Problems*, problem 8](https://www2.seas.gwu.edu/~simhaweb/champalg/tsp/papers/KarpOriginal.pdf).
Write \(b=|A|\). For a total order \(\sigma\) of the vertices, let \(H(\sigma)\) count the arcs whose source precedes their target. Then
\(\displaystyle \operatorname{fas}(G)=b-\max_\sigma H(\sigma).\)
Indeed, deleting the backward arcs of any order leaves an acyclic graph, giving one inequality. Conversely, after deleting a minimum feedback arc set, a topological order of the remaining graph makes every retained arc forward, giving the reverse inequality.
We therefore need to recover an order maximizing \(H\).
Set \(N=n\), and introduce the fixed root \(0\). Define
\(\displaystyle d=\binom n2,\qquad W=2^d,\qquad B=W(b+1).\)
Fix a bijection \(\ell\) from the unordered pairs, represented as \(i<j\), to \(\{0,\ldots,d-1\}\). For each rooted arborescence \(T\), define
\(\displaystyle C(T)=\sum_{\substack{i,j\in[n]\\i\ne j}}h_{(i,j)}(T),\)
\(\displaystyle H(T)=\sum_{(i,j)\in A}h_{(i,j)}(T),\)
\(\displaystyle J(T)=\sum_{1\le i<j\le n}2^{\ell(i,j)}h_{(i,j)}(T),\)
and
\(\displaystyle S(T)=B\,C(T)+W\,H(T)+J(T).\)
These quantities satisfy
\(\displaystyle 0\le C(T)\le d,\qquad 0\le H(T)\le b,\qquad 0\le J(T)\le W-1.\)
The bound on \(C\) holds because two distinct vertices cannot each be an ancestor of the other.
Moreover, \(C(T)=d\) precisely when \(T\) is a path starting at \(0\) and visiting all concept vertices. To see this, equality means every pair of concept vertices is comparable by ancestry. They therefore form a single chain. Consecutive vertices in that chain must be connected by an edge, because any intermediate vertex would also belong to the chain. The first concept vertex must likewise be a child of \(0\).
For a tree that is not such a path,
\(\displaystyle S(T)\le B(d-1)+Wb+(W-1)=Bd-1.\)
Every spanning path has score at least \(Bd\). Thus every maximizer of \(S\) is a spanning path.
On a path corresponding to an order \(\sigma\),
\(\displaystyle S(T)=Bd+W\,H(\sigma)+J(T).\)
Since \(J\) lies between \(0\) and \(W-1\), maximizing this expression first maximizes \(H\). Among orders with equal \(H\), it maximizes \(J\).
Distinct total orders have distinct vectors of pairwise comparisons. The powers of two in \(J\) encode that vector injectively, so distinct orders have distinct \(J\). Consequently:
Proven claim. There is a unique maximizing tree \(T^\star\), it is a spanning path, and its order maximizes \(H\). Since every score is an integer,
\(\displaystyle S(T^\star)-S(T)\ge 1\quad\text{for every }T\ne T^\star.\)
Use one worker type with mass \(1\) and error rate \(1/4\). Put
\(\displaystyle K=n^2+8.\)
For every ordered pair of distinct concept vertices, supply only answer-\(1\) frequency, as follows:
\(\displaystyle v_{1,(i,j),1}=K\left(B+W\,\mathbf 1_{\{(i,j)\in A\}}+t_{ij}\right),\)
where \(t_{ij}=2^{\ell(i,j)}\) if \(i<j\), and \(t_{ij}=0\) otherwise. All answer-\(0\) frequencies are zero.
These are nonnegative integers, hence admissible binary-rational frequencies. Each requires only \(O(n^2+\log n)\) bits, and there are \(n(n-1)\) supplied frequencies. The entire construction has polynomial bit length.
For error rate \(1/4\),
\(\displaystyle f_1(1\mid T,(i,j))=\frac14\,3^{h_{(i,j)}(T)}.\)
The factors \(1/4\), and the uniform prior, contribute only constants independent of \(T\). Hence the resulting posterior is exactly
\(\displaystyle Q(T)=\frac{3^{KS(T)}}{\sum_{U\in\mathcal T}3^{KS(U)}}.\)
Each concept vertex has \(n\) possible parents, so \(|\mathcal T|\le n^n\le 2^{n^2}\). Using the score gap,
\(\displaystyle \frac{Q(T\ne T^\star)}{Q(T^\star)} =\sum_{T\ne T^\star}3^{-K(S(T^\star)-S(T))} \le |\mathcal T|\,3^{-K} \le 2^{-8}.\)
It follows that \(Q(T\ne T^\star)\le 1/256\). Define its edge marginals by \(p_e=Q(e\in T)\). Then
\(\displaystyle p_e\ge \frac{255}{256}\quad(e\in T^\star),\qquad p_e\le \frac1{256}\quad(e\notin T^\star).\)
Thus constant-accuracy posterior edge marginals would identify \(T^\star\).
For arbitrary posterior edge marginals \(p_e\), the objective equals
\(\displaystyle F(\Lambda)=\log Z(\Lambda)-\sum_e p_e\lambda_e+\beta\|\Lambda\|_1.\)
Its cross-entropy term is nonnegative, so \(F(\Lambda)\ge\beta\|\Lambda\|_1\). Since \(F\) is continuous and \(\beta>0\), its minimum is attained.
Let \(s_e(\Lambda)=P_\Lambda(e\in T)\), and write
\(\displaystyle \phi(\Lambda)=\log Z(\Lambda)-\sum_e p_e\lambda_e.\)
Differentiating the finite partition sum gives
\(\displaystyle \partial_e\phi(\Lambda)=s_e(\Lambda)-p_e,\qquad \partial_e^2\phi(\Lambda)=s_e(\Lambda)(1-s_e(\Lambda))\le\frac14.\)
Suppose \(F(\widehat\Lambda)\le\min F+\epsilon\). We claim that every coordinate satisfies
\(\displaystyle |s_e(\widehat\Lambda)-p_e|\le\beta+\sqrt{\epsilon/2}.\)
To prove this, put \(g=s_e(\widehat\Lambda)-p_e\). If \(|g|\le\beta\), the claim is immediate. Otherwise put \(a=|g|-\beta>0\), and change coordinate \(e\) by \(t=-4a\,\operatorname{sign}(g)\). The second-derivative bound and the triangle inequality for the penalty give
\(\displaystyle F(\widehat\Lambda+t\mathbf e_e)-F(\widehat\Lambda) \le gt+\frac{t^2}{8}+\beta|t| =-2a^2. \)
Therefore \(2a^2\le F(\widehat\Lambda)-\min F\le\epsilon\), proving the claim.
With the fixed values \(\beta=1/64\) and \(\epsilon=1/8192\), this yields
\(\displaystyle |s_e(\widehat\Lambda)-p_e|\le\frac3{128}.\)
It remains to compute the model marginals \(s_e(\widehat\Lambda)\) in polynomial finite-precision time.
At \(\Lambda=0\), the model is uniform, so \(F(0)=\log|\mathcal T|\). Every valid returned optimizer therefore satisfies
\(\displaystyle \beta\|\widehat\Lambda\|_1 \le F(\widehat\Lambda) \le\log|\mathcal T|+\epsilon. \)
Consequently,
\(\displaystyle \|\widehat\Lambda\|_1\le64(n^2+1)=:M.\)
This numerical bound is polynomial in \(n\), even though the posterior frequencies can have exponentially large values.
Set \(\delta=1/(1024n)\). For each edge, compute a positive rational weight \(u_e\) satisfying
\(\displaystyle |\log u_e-\widehat\lambda_e|\le\delta.\)
This can be done in time polynomial in \(n\) and the bit length of \(\widehat\Lambda\). Here is an explicit justification.
For rational \(x\in[0,M]\), truncate the exponential Taylor series at degree \(r\). Taylor’s remainder and \( (r+1)!\ge((r+1)/e)^{r+1}\) imply relative error at most
\(\displaystyle \frac{x^{r+1}}{(r+1)!} \le\left(\frac{eM}{r+1}\right)^{r+1}. \)
Choose \(r+1\ge6M\) and \(2^{-(r+1)}\le\delta/2\). The relative error is then at most \(\delta/2\), which implies logarithmic error at most \(\delta\). For negative \(x\), take the reciprocal of the approximation to \(e^{-x}\). The number of terms and the bit lengths of all exact rational calculations are polynomial.
For every tree, its product of rounded weights differs from its original weight by a factor between \(e^{-n\delta}\) and \(e^{n\delta}\). After normalization, the probability ratio lies between \(e^{-2n\delta}\) and \(e^{2n\delta}\). Therefore every event probability changes by at most
\(\displaystyle e^{2n\delta}-1=e^{1/512}-1<\frac1{128}.\)
For completeness, the required determinant identity has a direct proof. Let \(\mathbf e_1,\ldots,\mathbf e_n\) be the standard basis and set \(\mathbf e_0=0\). Define an \(n\times n\) matrix whose column \(j\) is
\(\displaystyle \sum_{\substack{0\le i\le n\\i\ne j}}u_{ij}(\mathbf e_j-\mathbf e_i).\)
By multilinearity, its determinant is a sum over assignments of one parent to each concept vertex. An assignment containing a directed cycle contributes zero: the corresponding columns sum to zero around that cycle. Every other assignment reaches \(0\) and defines an arborescence. Ordering vertices with parents before children makes its selected-column matrix triangular with diagonal entries \(1\), so its determinant is \(1\).
Thus the matrix determinant equals
\(\displaystyle Z_u=\sum_{T\in\mathcal T}\prod_{e\in T}u_e.\)
Let \(Z_u^{(-e)}\) be the same determinant after setting weight \(u_e\) to zero. The exact rational marginal under these rounded weights is
\(\displaystyle \widetilde s_e=1-\frac{Z_u^{(-e)}}{Z_u}.\)
There are \(n^2\) edges. All these rational determinants can be computed exactly in polynomial time: clearing denominators gives integer matrices of polynomial bit length, and fraction-free elimination computes their determinants with polynomial bit complexity.
Combining the rounding estimate with Section 4 gives
\(\displaystyle |\widetilde s_e-p_e|<\frac1{128}+\frac3{128}=\frac1{32}.\)
Together with the posterior concentration bounds,
\(\displaystyle \widetilde s_e>\frac12\quad\Longleftrightarrow\quad e\in T^\star.\)
Hence every valid approximate optimizer permits polynomial-time recovery of the entire optimal path.
Given a Feedback Arc Set instance:
The construction is polynomial in the original input length. The decoder is polynomial in that length and the encoding length of the returned vector. A polynomial-time optimizer necessarily returns a polynomial-length vector, so the entire decision procedure would be polynomial-time.
This establishes \(\mathrm{NP}\)-hardness through a single optimizer call, already for the fixed constants stated above.
⟨structured verdict parsed — rendered above⟩
The proof is correct and resolves the assigned problem. It establishes \(\mathrm{NP}\)-hardness under the explicitly described reduction using one optimizer call and polynomial-time decoding. The hardness holds with the stated fixed worker, regularization, and accuracy parameters.
I found no major or minor mathematical issues requiring repair.
The cited source establishes the required hardness of directed Feedback Arc Set. Its reduction constructs a loopless digraph with an arc set rather than parallel arcs, so the restriction used by the prover is justified. [Karp, *Reducibility among Combinatorial Problems*, problem 8 and the reduction from Node Cover](https://studylib.net/doc/27985824/karp1972).
The identity \(\operatorname{fas}(G)=b-\max_\sigma H(\sigma)\) is correctly established in both directions:
Consequently, recovering any order maximizing \(H\) suffices to decide the source instance.
All three score bounds are valid:
The characterization \(C(T)=d\) precisely for spanning paths is correct. Equality makes all concept vertices comparable by ancestry. Since the only additional vertex is the root, the resulting chain includes every vertex of the tree. The explanation concerning consecutive vertices and the root rules out additional intervening vertices or branches.
The separation between paths and other trees is arithmetically correct:
\(B(d-1)+Wb+(W-1)=Bd-1\).
Every spanning path has score at least \(Bd\).
On paths, multiplication by \(W\) makes a one-unit improvement in \(H\) outweigh every possible change in \(J\). The binary encoding in \(J\) distinguishes all total orders, so the tie-breaking argument proves uniqueness. Integer-valued scores then give the claimed gap of at least \(1\).
The constructed society satisfies the input restrictions:
Because frequencies need not be normalized, their large numerical values are permitted. With \(b\le n(n-1)\), their binary encoding lengths are polynomial in \(n\).
The likelihood identity \(f_1(1\mid T,(i,j))=\frac14\,3^{h_{(i,j)}(T)}\) is exact. Summing the supplied frequency coefficients reproduces \(KS(T)\). The remaining likelihood factor and uniform prior are independent of \(T\), so the asserted posterior proportional to \(3^{KS(T)}\) follows exactly.
Each concept has \(n\) possible parents, giving \(|\mathcal T|\le n^n\le 2^{n^2}\). With \(K=n^2+8\), the score gap yields
\(|\mathcal T|3^{-K}\le 2^{-8}\).
The conversion from this posterior odds bound to \(Q(T\ne T^\star)\le 1/256\) is valid.
Both edge-marginal bounds follow immediately: edges of \(T^\star\) occur whenever \(T=T^\star\), whereas edges outside \(T^\star\) can occur only on the complementary event.
The expression
\(F(\Lambda)=\log Z(\Lambda)-\sum_e p_e\lambda_e+\beta\|\Lambda\|_1\)
is exact.
The cross-entropy is nonnegative because every tree probability is at most \(1\). Thus \(F(\Lambda)\ge\beta\|\Lambda\|_1\). Together with continuity and \(\beta>0\), this makes the objective coercive and ensures attainment of its minimum.
Differentiation is justified because the partition sum is finite. The derivative is the model edge marginal minus \(p_e\), and the diagonal second derivative is the variance of a binary edge indicator, bounded by \(1/4\).
The coordinate perturbation argument also handles the nonsmooth penalty correctly: it uses the triangle inequality rather than differentiating the absolute value. Substituting \(t=-4a\,\operatorname{sign}(g)\) into the stated upper bound gives exactly \(-2a^2\). Comparison with the attained minimum therefore proves
\(|s_e(\widehat\Lambda)-p_e|\le\beta+\sqrt{\epsilon/2}\).
For the specified constants,
\(\sqrt{\epsilon/2}=1/128\) and \(\beta=2/128\), giving the claimed \(3/128\) bound. This holds for every valid approximate optimizer.
Parameter bound. At zero parameters, \(F(0)=\log|\mathcal T|\). The approximation guarantee and coercive lower bound consequently give the stated bound
\(\|\widehat\Lambda\|_1\le64(n^2+1)\).
Thus every returned coordinate has polynomially bounded magnitude.
Rational exponential approximation. The Taylor remainder bound is valid for nonnegative arguments after dividing by the true exponential. The factorial estimate and the condition \(r+1\ge6M\) make the displayed error bound at most \(2^{-(r+1)}\). The additional accuracy condition gives relative error at most \(\delta/2\), sufficient for logarithmic error at most \(\delta\) in the stated range.
Taking reciprocals for negative arguments preserves the logarithmic error bound. The number of Taylor terms and the exact rational intermediate bit lengths are polynomial in \(n\) and the encoding length of the returned parameters.
Distribution perturbation. Every tree has exactly \(n\) edges, so its unnormalized weight changes by a factor between \(e^{-n\delta}\) and \(e^{n\delta}\). Applying the same bounds to the partition function gives the asserted normalized probability ratios. These imply the event-probability error bound. The numerical inequality \(e^{1/512}-1<1/128\) is correct.
Determinant formula. The supplied proof uses the correct matrix orientation for arborescences directed away from the root. Multilinearity produces one term for each parent assignment, with its product of weights as coefficient.
A directed cycle makes the corresponding selected columns linearly dependent. A cycle-free assignment must reach the root because every nonroot vertex has one assigned parent. For such an assignment, the parent-before-child ordering makes the selected-column matrix triangular with diagonal entries \(1\). Applying that ordering simultaneously to rows and columns preserves its determinant. Hence the determinant identity is correct.
Setting one weight to zero removes precisely the trees containing that edge, so
\(\widetilde s_e=1-Z_u^{(-e)}/Z_u\)
is exact. The denominator is positive because all original rounded weights are positive.
Clearing rational denominators produces integer matrices of polynomial bit length. Exact determinant computation by fraction-free elimination, including pivoting when needed, has polynomial bit complexity. Performing this computation for all \(n^2\) edges remains polynomial.
Threshold decoding. The combined marginal error is strictly below \(1/32\). This is comfortably smaller than the separation supplied by the posterior bounds \(255/256\) and \(1/256\). Thresholding at \(1/2\) therefore identifies exactly the edges of \(T^\star\).
The decoder recovers the unique spanning path and hence an order maximizing the source objective. The final test \(b-H(\sigma^\star)\le k\) correctly decides Feedback Arc Set.
The construction has polynomial input length. Decoding is polynomial in the source size and returned-vector encoding length. A polynomial-time optimizer necessarily produces a polynomial-length output, so the claimed polynomial-time consequence follows.
The proof covers arbitrary valid optimizer outputs; it does not require a preferred optimizer, access to posterior marginals, or a posterior sampling oracle.
The boundary case \(n=1\) is consistent: \(d=0\), the comparison-index set is empty, and there is exactly one rooted tree. Empty arc sets also cause no failure. The reduction needs only a hard family of nonempty source graphs and does not depend on degenerate cases.
None is required. The conclusion should retain the reduction interpretation already stated in the write-up: hardness through one approximate-optimizer call followed by polynomial-time decoding.
⟨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.