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 you have read our privacy policy.