# Hardness of computing entropy of a function on uniform input distribution

Let $$p \geq q \in \mathbb{N}_+$$, and let $$L_\mathsf{max-entropy} := \{(f,k) \in \{0,1\}^{\lambda^p} \times \{0,1\}^{\log\lambda} | \lambda \in \mathbb{N} \wedge \mathrm{H}(\underbrace{C_f(\mathcal{U}_{\lambda^q})}_{\in \{0,1\}^{\lambda}}) \leq k\}$$ where $$C_f : \{0,1\}^{\lambda^q} \to \{0,1\}^{\lambda}$$ is interpreted as a circuit computing the function indexed by $$f$$, $$\mathrm{H}$$ is the Shannon entropy and $$\mathcal{U}_{\lambda^q}$$ is the uniform distribution on $$\{0,1\}^{\lambda^q}$$.

Intuitively, $$L_\mathsf{max-entropy}$$ consists of pairs of circuit descriptions $$f$$ and thresholds $$k$$ s.t. $$C_f$$ evaluated on a uniform input distribution has entropy at most $$k$$.

Naturally, $$L_\mathsf{max-entropy} \in \mathsf{PSPACE}$$. This is because for any distribution $$\mathcal{Y}$$ (here $$\mathcal{Y} = C_f(\mathcal{U}_{\lambda^q})$$) its Shannon entropy $$\mathrm{H}(\mathcal{Y}) = -\sum_{y \in \mathcal{Y}} \mathsf{P}[\mathcal{Y} = y] \log_2(\mathsf{P}[\mathcal{Y} = y])$$ as a sum over all its elements. For each output $$y \in \{0,1\}^{\lambda}$$ its probability can be computed by counting all corresponding inputs $$X_y = \{x \in \{0,1\}^{\lambda^q} | y = C_f(x)\}$$, i.e., $$\mathsf{P}[\mathcal{Y} = y] = |X_y| / 2^{\lambda^q}$$.

Is $$L_\mathsf{max-entropy}$$ $$\mathsf{PSPACE}$$-complete or contained in a smaller class?