Answer: \(\#\mathrm{P}\)-hard, hence \(\mathrm{NP}\)-hard, under polynomial-time Turing reductions for each specified output representation.
Theorem 1 — class: hardness
Given \(n\) candidates, a finite support of trader portfolio types with rational masses \(\mu_t\) summing to one, and per-capita holdings \(h_t(i,j)\) for each candidate-position security, set \(Q_{ij}=\sum_t\mu_t h_t(i,j)\). For a designated security \(\langle i\mid j\rangle\), compute its exact LMSR quote and normalizer \(Z=\sum_{\sigma\in S_n}\exp\!\left(\frac{1}{b}\sum_i Q_{i,\sigma(i)}\right)\), hence the cost \(b\log Z\).
There are \(m=n\geq 2\) candidates and positions; outcomes are permutations \(\sigma\in S_m\). Security \(\langle i\mid j\rangle\) pays one unit exactly when \(\sigma(i)=j\), and zero otherwise.
A society is given by its support: a list of \(\tau\) portfolio types with positive binary-rational masses \(\mu_t\), summing to one. Here \(\tau\) is the support size, not the number of possible types.
Each type supplies signed binary-rational per-capita holdings \(h_t(i,j)\); negative holdings represent short positions. The liquidity parameter \(b>0\) is a binary rational, and \(L\) is the total input bit length, including the designated indices \(i,j\).
Set \(Q_{ij}=\sum_t\mu_t h_t(i,j)\) and \(s_\sigma=b^{-1}\sum_k Q_{k,\sigma(k)}\). Define \(Z=\sum_{\sigma\in S_m}\exp(s_\sigma)\), \(N_{ij}=\sum_{\sigma\in S_m:\sigma(i)=j}\exp(s_\sigma)\), the instantaneous quote \(p_{ij}=N_{ij}/Z\), and the cost \(C=b\log Z\), using the natural logarithm.
For exact finite output, represent each exponential sum by its collected list of distinct rational exponents and positive integer coefficients, all in binary; represent the quote by the numerator and denominator lists and the cost by the logarithm of the normalizer list.
Is computing the exact designated LMSR quote, normalizer, and cost in this representation possible in time polynomial in \(m,\tau,L\), or is it \(\mathrm{NP}\)-hard under polynomial-time Turing reductions?
For unrestricted outstanding-share quantities, exact candidate-position LMSR prices and costs are \(\#\mathrm{P}\)-hard; the published reduction uses logarithmic share quantities. [Chen et al.](https://ai.stanford.edu/~nlambert/papers/Chen_et_al_(EC_2008).pdf)
That result does not establish hardness for binary-rational holdings with the exact-output convention specified here.
Computing each of the exact designated quote, normalizer, and cost in the specified representation is \(\#\mathrm{P}\)-hard under polynomial-time Turing reductions, and therefore \(\mathrm{NP}\)-hard. This holds already when \(\tau=1\), \(b=1\), and every holding belongs to \(\{0,1\}\).
The hardness reduction uses only instances whose output lists have polynomial length. Separately, general instances can require factorially many output records, which unconditionally rules out polynomial time in the input parameters for producing these explicit lists.
We use Valiant’s theorem: computing the permanent of a square zero–one matrix is \(\#\mathrm{P}\)-complete under polynomial-time Turing reductions. Here the permanent is defined by
\(\operatorname{perm}(A)=\sum_{\sigma\in S_m}\prod_{k=1}^{m}A_{k,\sigma(k)}\).
The theorem applies specifically to matrices with entries in \(\{0,1\}\). See [Valiant, *The complexity of computing the permanent*, Theorem 1](https://www.math.cmu.edu/users/af1p/Teaching/MCC17/Papers/permanent.pdf).
Given \(A\in\{0,1\}^{m\times m}\), with \(m\geq2\), construct a society with
\(\tau=1\), \(\mu_1=1\), \(b=1\), and \(h_1(k,\ell)=A_{k\ell}\).
For the quote, designate \((i,j)=(1,1)\).
These satisfy all input requirements: the sole mass is positive and sums to one, and all holdings and the liquidity parameter are binary rationals. The construction has polynomial input length. Since \(Q=A\), each permutation has exponent
\(s_\sigma=\sum_{k=1}^{m}A_{k,\sigma(k)}\in\{0,1,\ldots,m\}\).
Define
\(c_r=\bigl|\{\sigma\in S_m:s_\sigma=r\}\bigr|\)
for \(r\in\{0,\ldots,m\}\). The required collected normalizer list represents
\(Z=\sum_{r=0}^{m}c_r\exp(r)\),
with records of coefficient zero omitted.
Because each summand in \(s_\sigma\) is either zero or one, \(s_\sigma=m\) holds exactly when every selected entry \(A_{k,\sigma(k)}\) equals one. Likewise, the product \(\prod_{k=1}^{m}A_{k,\sigma(k)}\) equals one exactly in this case and equals zero otherwise. Consequently,
\(c_m=\operatorname{perm}(A)\).
Thus one normalizer query computes the permanent: read the coefficient of exponent \(m\), returning zero if that exponent is absent.
The oracle response has polynomial length. There are at most \(m+1\) records. Every exponent requires \(O(\log m)\) bits, and every coefficient is at most \(m!\), requiring \(O(m\log m)\) bits. Hence the full list requires \(O(m^2\log m)\) bits, and extracting \(c_m\) takes polynomial time.
Matrices of order less than two can be handled directly, so the restriction \(m\geq2\) does not affect the reduction.
Under the stipulated quote representation, the output consists of the collected lists for the actual numerator \(N_{11}\) and denominator \(Z\). Its denominator therefore supplies exactly the normalizer list used above. Reading its coefficient at exponent \(m\) computes \(\operatorname{perm}(A)\).
The numerator also has polynomial length on these instances: its exponents lie in \(\{0,\ldots,m\}\), and its coefficients are at most \((m-1)!\). Thus the entire quote response has polynomial length.
For the cost, the representation explicitly contains the normalizer list inside the logarithm. Since our construction sets \(b=1\), the cost is represented as
\(C=\log\bigl(\sum_{r=0}^{m}c_r\exp(r)\bigr)\).
Again, reading the coefficient at exponent \(m\) computes the permanent.
Therefore the permanent polynomial-time Turing-reduces to each requested computation. By Valiant’s theorem, each computation is \(\#\mathrm{P}\)-hard.
To make the implication to \(\mathrm{NP}\)-hardness explicit, counting satisfying assignments belongs to \(\#\mathrm{P}\), so it has a polynomial-time Turing reduction to the zero–one permanent. Replace each permanent query in that reduction by the construction above and coefficient extraction. A Boolean formula is satisfiable exactly when the resulting assignment count is positive. All replacement queries and responses have polynomial length, giving the required polynomial-time Turing reduction for satisfiability.
This argument uses integer holdings throughout and requires no numerical evaluation of exponentials or logarithms.
For each \(m\geq2\), take \(\tau=1\), \(\mu_1=b=1\), and set
\(h_1(k,\ell)=2^{(k-1)m+(\ell-1)}\)
for \(1\leq k,\ell\leq m\).
Each holding has at most \(m^2\) binary digits, so the total input length is \(L=O(m^4)\). For a permutation,
\(s_\sigma=\sum_{k=1}^{m}2^{(k-1)m+(\sigma(k)-1)}\).
The map \((k,\ell)\mapsto(k-1)m+(\ell-1)\) is injective. Consequently, the displayed sum has a binary digit equal to one exactly at the indices of the selected candidate–position pairs. Distinct permutations select distinct sets of pairs, and uniqueness of binary expansion implies that their exponents are distinct.
The collected normalizer therefore has exactly \(m!\) records, each with coefficient one. The quote denominator and the cost’s normalizer list contain those same records.
Any algorithm writing these explicit outputs must take at least \(\Omega(m!)\) time. Since \(m!\) grows faster than every polynomial in \(m\), while \(\tau=1\) and \(L=O(m^4)\), no algorithm can produce the required outputs in time polynomial in \(m,\tau,L\) on all inputs, irrespective of complexity-class separations.
The coefficient reduction establishes computational hardness even when this output-length obstruction is absent.
⟨structured verdict parsed — rendered above⟩
Proved. The output correctly establishes that each requested computation is \(\#\mathrm{P}\)-hard, hence \(\mathrm{NP}\)-hard, under polynomial-time Turing reductions in the stipulated representation. The reduction uses polynomial-length responses and satisfies every input restriction. The independent output-length obstruction is also correct.
No major or minor mathematical issues were found.
The prover states precisely the needed theorem: computing the permanent of a square zero–one matrix is \(\#\mathrm{P}\)-complete under polynomial-time Turing reductions.
This matches [Valiant’s Theorem 1](https://www.math.cmu.edu/users/af1p/Teaching/MCC17/Papers/permanent.pdf). The paper’s reduction framework uses polynomial-time oracle reductions for functions. Thus the theorem supplies the reduction notion claimed by the prover.
The input matrix in the construction is square and has entries in \(\{0,1\}\), so the theorem’s hypotheses are satisfied. Orders below two are explicitly handled directly; excluding them from the constructed societies does not affect hardness.
The construction sets
\[
\tau=1,\qquad \mu_1=1,\qquad b=1,\qquad h_1(k,\ell)=A_{k\ell}.
\]
Every parameter satisfies the task:
The aggregate holdings are exactly \(Q=A\). Consequently, the claimed exponent formula follows directly from the task’s definition.
Every exponent is the sum of \(m\) zero–one entries, so it lies in \(\{0,\ldots,m\}\). The coefficient \(c_r\) counts precisely the permutations with exponent \(r\), as required by the collected-list representation.
The decisive equivalence is correct:
\[
s_\sigma=m
\quad\Longleftrightarrow\quad
A_{k,\sigma(k)}=1\text{ for every }k.
\]
For zero–one entries, the product in the permanent definition equals one exactly under this condition and otherwise equals zero. Hence \(c_m=\operatorname{perm}(A)\).
Reading the coefficient at exponent \(m\) therefore returns the permanent. If that exponent is absent, its coefficient is zero, consistent with the convention that zero-coefficient records are omitted. This also covers matrices having no perfect matching.
No numerical evaluation of exponentials, uniqueness theorem for exponential values, or approximation argument is needed: extraction uses the prescribed list itself.
There are at most \(m+1\) normalizer records. Integer exponents between zero and \(m\) require \(O(\log m)\) bits, and coefficients bounded by \(m!\) require \(O(m\log m)\) bits. The claimed bound of \(O(m^2\log m)\) for the list is valid.
Scanning this list and identifying exponent \(m\) takes polynomial time. Thus the reduction does not hide excessive time in reading an exponentially long oracle response.
For the quote, the task specifies the actual numerator and denominator lists. Its denominator is therefore the normalizer list already used in the reduction. The prover correctly relies on this representation requirement.
The numerator contains exactly the permutations satisfying \(\sigma(1)=1\), of which there are \((m-1)!\). Its exponents still lie in \(\{0,\ldots,m\}\), so both its coefficient bound and polynomial response-length claim are correct, including \(m=2\).
For the cost, setting \(b=1\) gives \(C=\log Z\). The stipulated representation exposes the normalizer list inside this expression, so the same coefficient extraction applies.
Accordingly, the construction separately reduces the permanent to each requested computation.
Composing the permanent reduction with Valiant’s theorem establishes \(\#\mathrm{P}\)-hardness under polynomial-time Turing reductions.
The explicit implication to \(\mathrm{NP}\)-hardness is also valid: counting satisfying assignments belongs to \(\#\mathrm{P}\), the count can be obtained through the composed reductions, and satisfiability is equivalent to that count being positive. The replacement society queries and their responses remain polynomial in size.
The prover does not incorrectly infer satisfiability hardness merely from testing whether a zero–one permanent is positive.
In the second family, each holding is a power of two whose binary representation has at most \(m^2\) digits. With \(m^2\) holdings, the bound \(L=O(m^4)\) is correct.
The exponent indices assigned to matrix entries are distinct. Each permutation selects distinct powers of two, so the resulting sum has exactly the corresponding binary digits set, without carries. Distinct permutations select different sets of entries and therefore yield different exponents.
Thus the normalizer has exactly \(m!\) records, each with coefficient one. The prescribed quote denominator and cost representation contain the same records.
Writing these lists requires at least \(\Omega(m!)\) time. Because \(L=O(m^4)\) and \(\tau=1\), this exceeds every polynomial in the stated input parameters. The unconditional impossibility of polynomial-time explicit output on all inputs follows correctly.
None is required. The argument resolves the target in its specified representation; it does not claim hardness for a different representation that omits the underlying exponential-sum lists.
⟨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.