4
$\begingroup$

There is a problem that I am working on. I have shown that the problem is NP Hard, but I haven't been able to show that it is in NP. But the problem is also known to be in EXP. My gut feeling is that the problem is PSPACE-complete. I am leaving aside PSPACE-hardness for now. Even if I have to prove that the problem is in PSPACE, it doesn't look so easy. My options are:

  1. Write down a polynomial space algorithm
  2. Reduce my problem to a QBF formula
  3. Using Savitch theorem, PSPACE=NPSPACE. Therefore try to come up with a certificate for the problem that can be verified using polynomial space.

If I try to use the 3rd approach, do I have to ensure that the certificate is polynomially sized. So basically what I am asking is if the certificate of the NDTM is stored in the working memory tape or the input memory tape? If it is stored in the working memory, then I could use up exponential memory for the certificate, thus making it not a problem in PSPACE.

Improve this question
$\endgroup$
1
  • $\begingroup$ PS: The certificate I have right now is exponential in length. But verification need not take so much space since I bring only what I want into the working memory at once. That is why I am having this doubt about whether this is enough, or I need to ensure polynomial sized certificate (or that the certificate is assumed to be stored in the working tape) $\endgroup$
    – Mohith Jagalmohanan
    Commented Jun 17, 2021 at 6:15

2 Answers 2

Reset to default
5
$\begingroup$

It's OK for the certificate to be exponentially long only if (1) the space consumption of the verifier is polynomial in the size of the problem instance (it is not allowed to use space polynomial in the size of the certificate) and (2) the verifier only accesses the certificate in a read-once fashion: once it reads a particular part of the certificate, it is erased, and the verifier cannot ever read it again.

Conceptually, you can view the certificate as the record of nondeterministic choices made by the nondeterministic algorithm that proves the problem is in NPSPACE. That algorithm can only use polynomial space but can use exponential time, so it might make exponentially many nondeterministic choices, hence why the certificate can potentially be be exponentially long (and hence why the verifier must use space that is polynomial in the size of the problem instance, not the size of the certificate).

My thanks to Emil Jeřábek for pointing out that my original answer was wrong. As he writes:

While an NPSPACE machine can use exponential time, and the natural way to certify its nondeterministic choices is using an exponential-size certificate that can be verified in polynomial space, this is not by itself enough to guarantee that the language is in (N)PSPACE, as exactly the same is true of NEXP. That is, any NEXP language has exponential-size certificates that can be verified by a PSPACE (or even coNP) machine that can only access a constant-size part of the witness at any given time: just take the transcript (sequence of configurations) of an accepting run of the NEXP machine as the certificate. The correctness of the transcript can be verified by checking local conditions that only involve a constant number of cells of at most two configurations at the same time, hence it can be easily done in polynomial space. What distinguishes NPSPACE from NEXP is that an NPSPACE machine cannot write down the certificate, and if it generates its parts nondeterministically on the fly, it has no way of ensuring that it generates the same bits if it "reads" the same chunk of the certificate twice. That is, it can only access the certificate in a read-once fashion: once it reads a particular part of the certificate, it is erased, and the verifier cannot ever read it again.

Improve this answer
$\endgroup$
10
  • 1
    $\begingroup$ ... of the NEXP machine as the certificate. The correctness of the transcript can be verified by checking local conditions that only involve a constant number of cells of at most two configurations at the same time, hence it can be easily done in polynomial space. What distinguishes NPSPACE from NEXP is that an NPSPACE machine cannot write down the certificate, and if it generates its parts nondeterministically on the fly, it has no way of ensuring that it generates the same bits if it “reads” the same chunk of the certificate twice. That is, it can only access the certificate in a ... $\endgroup$
    – Emil Jeřábek
    Commented Jun 18, 2021 at 9:19
  • 1
    $\begingroup$ ... read-once fashion: once it reads a particular part of the certificate, it is erased, and the verifier cannot ever read it again. $\endgroup$
    – Emil Jeřábek
    Commented Jun 18, 2021 at 9:20
  • 1
    $\begingroup$ @EmilJeřábek, oh gosh, thank you for explaining that to me. You are very gracious; it's not just misleading, my answer is plain wrong. I would prefer to delete it as it is so faulty, but unfortunately I cannot delete it as it has been accepted. Do you have any advice on the best way to correct it? Also, may I quote from your comments? $\endgroup$
    – D.W. ♦
    Commented Jun 18, 2021 at 18:11
  • 1
    $\begingroup$ Well, it’s up to you how to formulate it; I guess the most important thing is that an NSPACE machine has no facility to read bits of the exponential certificate twice. You may use anything I wrote in the comments, no problem. $\endgroup$
    – Emil Jeřábek
    Commented Jun 19, 2021 at 5:54
  • 1
    $\begingroup$ @MohithJagalmohanan Any language may have many different types of certificates whose verifiers may have different properties. You are mixing up two things. (1) If a language has exponential-size certificates that are verifiable in EXP, then it is in NEXP. (2) If a language is in NEXP, then it has exponential-size certificates (possibly different from those previously supplied in (1)) that are verifiable in PSPACE (by a possibly different verifier than previously given in (1)). $\endgroup$
    – Emil Jeřábek
    Commented Jun 22, 2021 at 13:43
4
$\begingroup$

Lets say you have some certificate of length $s>>poly(n)$, and you are only allowed to store at most $poly(n)$ memory. Assuming you are capable of verifying "chunks" from the certificate of size $poly(n)$ at a time, it really wont matter what $s$ is.

Try to think of the following:

  1. We iterate through all possible strings of size $poly(n)$ for the first "chunk", and verify if at least one of them makes you accept.
  2. We delete that "chunk", and do the same for the "second chunk".
  3. Do step 2 again until you have checked $\frac{s}{poly(n)}$ "chunks"

This will guarantee you will never use more than $poly(n)$ space, but will allow you to simulate any certificate size that you can verify in small parts. Hence, your language is in $PSPACE$.

I hope this helped!

Improve this answer
$\endgroup$
1
  • $\begingroup$ Oh yes. This surely helped. Thank you! $\endgroup$
    – Mohith Jagalmohanan
    Commented Jun 17, 2021 at 14:25

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.