The particular case of language universality (are all words accepted ?) is PSPACE-complete for regular expressions or NFAs. It answers your question: in general the problem stays PSPACE-complete even for fixed $E_1$, since language universality corresponds to $E_1=\Sigma^*$. It is indeed hard to find a modern readable PSPACE-hardness proof for regular expression universality, as it is now considered folklore. Here is a quick proof scheme that allows you to rebuild the proof: ------ Consider a Turing Machine $M$ on alphabet $\Sigma$ using polynomial space $p(n)$, and let $w\in\Sigma^*$ be an input word for $M$. We will build a regular expression $e$ that accepts all words if and only if $M$ has no accepting run on $w$. Consider the language $L_M$ consisting of words of the form $\$C_0\$ C_1\$\dots\$ C_f\$$, where each $C_i$ is a configuration of $M$ of length exactly $p(n)$, $C_0$ is the initial configuration with $w$ on the tape, $C_f$ is accepting ,and each $C_i\to C_{i+1}$ is a valid transition of $M$. A word in $L$ describes an accepting run of $M$. We build $e$ on alphabet $\Sigma'=\Sigma\cup\{\$\}$ such that $e$ accepts exactly words that are not in $L_M$, by looking for a violation of the definition of $L_M$. The expression $e$ will be a big disjunction $e_1+e_2+\dots+e_k$, where each $e_i$ looks for a different kind of violation. For instance $$e_1=(\Sigma')^*\$(\Sigma^{<p(n)}+\Sigma^{>p(n)})\$(\Sigma')^*$$ looks for a violation of the fact that each $C_i$ has size exactly $p(n)$. The most tricky part is guessing a violation between $C_i$ and $C_{i+1}$: the expression can compare a local pattern in $C_i$ and its image in $C_{i+1}$, using $t(\Sigma')^{p(n)}t'$, where $t$ and $t'$ are expressions for local patterns. With this we can guess a violation of the transition function of $M$ on a local pattern, or a violation of the identity outside of this pattern. In the end, we obtain that $$L(e)\neq (\Sigma')^*\text{ if and only if }L_M\neq\emptyset\text{ if and only if $M$ accepts }w$$ therefore we reduced (polynomially) an arbitrary PSPACE problem to universality of a regular expression. I left out some details, but this should allow you to build a complete proof. You can also reduce from other PSPACE-complete problems such as [TQBF][1]. ------- Of course, as pointed out by Michael Wehar in the comments, for others $E_1$ the problem can become simpler. Classifying the complexity of this problem has been studied extensively in [this paper][2] \[1\] for equivalence, containment, and covering. You can see a summary of the results for the equivalence problem in [this answer][3] (there does exist NP-complete cases). As for your remark on squaring: allowing squaring in regular expressions make the inclusion and universality problem EXPSPACE-complete \[2\]. Remark that this can be seen in the proof scheme above, since $(\Sigma')^{p(n)}$ can now be expressed with a logarithmic-size expression in $p(n)$ using its binary decomposition, so we can go up to an exponential $p(n)$ while keeping the size of the expression polynomial. \[1\] *On the equivalence, containment, and covering problems for the regular and context-free languages* Harry B.Hunt, Daniel J.Rosenkrantz, Thomas G.Szymanski. Journal of Computer and System Sciences. Volume 12, Issue 2, April 1976, Pages 222-268 \[2\] *The equivalence problem for regular expressions with squaring requires exponential space*. Meyer, A.R. and L. Stockmeyer. 13th IEEE Symposium on Switching and Automata Theory, Oct 1972, pp.125–129. [1]: https://en.wikipedia.org/wiki/True_quantified_Boolean_formula [2]: https://www.sciencedirect.com/science/article/pii/S0022000076800384?via%3Dihub [3]: https://cstheory.stackexchange.com/a/34739/8953