Prove $PSPACE$-completeness of the language $READALLEXACT$ = $\{$$(M, x, 1^ s , t)$ | $A$ deterministic Turing machine $M$ on input $x$ reads all bits of the input in exactly $t$ steps and using no more than $s$ memory cells (consider that a bit is read if the machine head has ever been over it; after reading the input the machine can use more memory; define the exact memory allocation model determine so that the assignment is correct)$\}$.
To prove that READALLEXACT is PSPACE-complete, we can reduce a known PSPACE-complete problem, such as QBF (Quantified Boolean Formula) to it. First, we can encode a QBF in the form of (Q,B) where Q is the quantifier prefix and B is the propositional matrix. We can then construct a Turing machine that takes in this encoded QBF and verifies that all quantifiers and propositions have been read in exactly t steps and using no more than s memory cells. We can show that this reduction is polynomial in the size of the input, and that the constructed machine halts if and only if the QBF is true. Therefore, READALLEXACT is at least as hard as QBF, and since QBF is known to be PSPACE-complete, READALLEXACT is PSPACE-complete. It's also worth noting that due to the nature of the problem, it's not possible to bound the time and memory usage of the machine in a non-trivial way, so this problem is not in NP neither in co-NP
Is my proof correct or no? if it is not can u help me fix it?:(
