MathDB

Misha is currently taking a Complexity Theory exam, but he seems to have forgotten a lot of the material! In the question, he is asked to fill in the following boxes with

\subseteq

and

\subsetneq

to identify the relationship between different complexity classes:

\mathsf{NL}\ \fbox{\phantom{tt}}\ \mathsf{P}\ \fbox{\phantom{tt}}\ \mathsf{NP}\ \fbox{\phantom{tt}}\ \mathsf{PH}\ \fbox{\phantom{tt}}\ \mathsf{PSPACE}\ \fbox{\phantom{tt}}\ \mathsf {EXP}

and

\mathsf{coNL}\ \fbox{\phantom{tt}}\ \mathsf{P}\ \fbox{\phantom{tt}}\ \mathsf{coNP}\ \fbox{\phantom{tt}}\ \mathsf{PH}

Luckily, he remembers that

\mathsf{P} \neq \mathsf{EXP}

\mathsf{NL} \neq \mathsf{PSPACE}

\mathsf{coNL} \neq \mathsf{PSPACE}

, and

\mathsf{NP} \neq \mathsf{coNP}\implies \mathsf{P}\neq \mathsf{NP} \land \mathsf{P}\neq \mathsf{coNP}

. How many ways are there for him to fill in the boxes so as not to contradict what he remembers?

Problem Statement