Question

Question: Let${\mathbf{E}}_{\mathbf{REX}\hat{\mathbf{I}}}$

Short answer

We know that$\mathbf{PSPACE}\mathbf{\varnothing }\mathbf{EXSPACE}$ i.e., the problem of any EXSPACE-complete cannot be in PSPACE.

Step-by-step solution

Using Regular expression with exponentiation

Consider the statement${\mathbf{E}}_{\mathbf{REX}\hat{\mathbf{I}}}\mathbf{=}\mathbf{\{}\overline{)<R>}$ R is regular expression with exponentiation and

$\mathbf{L}\mathbf{\left(}\mathbf{R}\mathbf{\right)}\mathbf{=}\mathbf{\varnothing }$}

From the above statement it can be understood that R is a regular expression and the language, which contains this regular expression consists NULL values.

Applying the concept of intractability

${\mathbf{E}}_{\mathbf{REX}\hat{\mathbf{I}}}$is said to be intractable because it can be demonstrated in such a manner that is complete for the class EXSPACE.

From the above statements we can conclude that “any EXSPACE-complete problem cannot be in PSPACE and it is much less in P”.

Because PSPACE will be same as EXSPACE which is contradicting the corollary discussed above.

Hence, it can be said that${\mathbf{E}}_{\mathbf{REX}\hat{\mathbf{I}}}\mathbf{\in }\mathbf{P}$