<p>It is my understanding that the necessity of numerical precision can be an obstacle when trying to show a decision problem's membership in a particular complexity class. For example, I believe it is open whether Euclidean TSP is in NP, because it is unknown whether the following simple-sounding decision problem is in NP:</p>
<p><em>Square-Root Sum</em>: Given <span class="math-container">$ a_1,\dots,a_n; k $</span>, determine whether or not <span class="math-container">$  \sum_i \sqrt{a_i} \leq k.  $</span></p>
<p>With this in mind, I am curious what is known about the complexity of the corresponding decision problem for computing Shannon entropy.</p>
<p><em>Compute Entropy</em>: Given a discrete distribution <span class="math-container">$p$</span>, determine whether or not <span class="math-container">$ H(p) \le k$</span>.</p>
<p>I am particularly interested in whether or not this decision problem is in NP. There are some senses where this seems this might be easier than computing the sum of square-roots, because the terms of <span class="math-container">$\sum_i x_i \log\left(\frac{1}{x_i}\right)$</span> can be combined into a monomial, but it is not obvious to me whether this decision problem is in NP. I believe I have seen some casual claims where particular combinatorial optimization problems with such an objective function are implied to be trivially in NP, but it is unclear to me how one would show this.</p>

CC BY-SA 4.0
2022-10-04T07:08:02.413Z
Nitpick: How is the discrete distribution $p$ specified?  How do you plan to represent the probabilities (which might be real numbers)?  Is $k$ restricted to be an integer?  (In contrast, in square-root sum, $a_1,\dots,a_n,k$ are integers, so there are no issues with representation.)
D.W.
CC BY-SA 4.0
2022-10-04T18:39:34.143Z
That's a great question. I would learn towards all inputs being encoded as rational numbers, but I would be happy to hear any thoughts involving representations that potential answerers believe are insightful.
Spencer Compton
CC BY-SA 4.0
2022-10-04T20:29:27.853Z
If the distributions are given as circuits (from which one can sample), then even approximating is hard, but that seems to deviate quite a bit from what you have in mind: https://dash.harvard.edu/handle/1/4728400
Clement C.
CC BY-SA 4.0
2022-10-06T21:34:04.557Z
Side note: you can generalize this to asking if the KL div b/w 2 distributions is at most t; or, more generally, for which f-divergences the decision problem is in NP. (I believe it is for squared Hellinger and χ².)
Clement C.
CC BY-SA 4.0
2022-10-06T22:10:53.257Z
Are you willing to assume anything about the sizes of the binary representations of $k$ and the rational numbers defining $p$, as a function of the number $n$ of elements in $p$?  E.g. each number can be represented in $O(\log n)$ bits?
Neal Young
CC BY-SA 4.0
2022-10-07T00:20:12.610Z
@NealYoung this seems like it could be reasonable to me, and sounds interesting if it permits entropy to be efficiently computed. As my main motivation comes from existing combinatorial optimization problems where aspects like the input representation seem not so well-defined, I mostly defer to the community regarding what are reasonable assumptions for representation.
Spencer Compton
<cc.complexity-theory>
Complexity of Computing Shannon Entropy
Spencer Compton
# Complexity of Computing Shannon Entropy

(Asked by: username_0 on 2022-10-03)

It is my understanding that the necessity of numerical precision can be an obstacle when trying to show a decision problem's membership in a particular complexity class. For example, I believe it is open whether Euclidean TSP is in NP, because it is unknown whether the following simple-sounding decision problem is in NP:

*Square-Root Sum*: Given $ a\_1,\dots,a\_n; k $, determine whether or not $ \sum\_i \sqrt{a\_i} \leq k. $

With this in mind, I am curious what is known about the complexity of the corresponding decision problem for computing Shannon entropy.

*Compute Entropy*: Given a discrete distribution $p$, determine whether or not $ H(p) \le k$.

I am particularly interested in whether or not this decision problem is in NP. There are some senses where this seems this might be easier than computing the sum of square-roots, because the terms of $\sum\_i x\_i \log\left(\frac{1}{x\_i}\right)$ can be combined into a monomial, but it is not obvious to me whether this decision problem is in NP. I believe I have seen some casual claims where particular combinatorial optimization problems with such an objective function are implied to be trivially in NP, but it is unclear to me how one would show this.

**Tags:** cc.complexity-theory
> **Comments:**
> **username_1**: Nitpick: How is the discrete distribution $p$ specified?  How do you plan to represent the probabilities (which might be real numbers)?  Is $k$ restricted to be an integer?  (In contrast, in square-root sum, $a_1,\dots,a_n,k$ are integers, so there are no issues with representation.)  
> **username_0**: That's a great question. I would learn towards all inputs being encoded as rational numbers, but I would be happy to hear any thoughts involving representations that potential answerers believe are insightful.  
> **username_2**: If the distributions are given as circuits (from which one can sample), then even approximating is hard, but that seems to deviate quite a bit from what you have in mind: https://dash.harvard.edu/handle/1/4728400  
> **username_2**: Side note: you can generalize this to asking if the KL div b/w 2 distributions is at most t; or, more generally, for which f-divergences the decision problem is in NP. (I believe it is for squared Hellinger and χ².)  
> **username_3**: Are you willing to assume anything about the sizes of the binary representations of $k$ and the rational numbers defining $p$, as a function of the number $n$ of elements in $p$?  E.g. each number can be represented in $O(\log n)$ bits?  
> **username_0**: @NealYoung this seems like it could be reasonable to me, and sounds interesting if it permits entropy to be efficiently computed. As my main motivation comes from existing combinatorial optimization problems where aspects like the input representation seem not so well-defined, I mostly defer to the community regarding what are reasonable assumptions for representation.  

---

## 0 answers

