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?



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.