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?:(

  • $\begingroup$ We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. $\endgroup$
    – Nathaniel
    Jan 14 at 15:30
  • $\begingroup$ Also, given the abstraction of the language, wouldn't it be easier to make a reduction directly from any language in $\mathsf{PSPACE}$ (meaning recognized by a deterministic Turing machine in polyspace)? $\endgroup$
    – Nathaniel
    Jan 14 at 15:31
  • $\begingroup$ I don't think so:( $\endgroup$
    – Vahan
    Jan 14 at 15:40
  • $\begingroup$ We require you to credit the original source of all copied material: cs.stackexchange.com/help/referencing. Where does the material in the quote block come from? Please credit the original source in accordance with our rules. $\endgroup$
    – D.W.
    Jan 14 at 21:32


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.