patternMinor
Should the certificate for NPSPACE be polynomial in size?
Viewed 0 times
certificatethepolynomialsizenpspaceforshould
Problem
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:
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.
- Write down a polynomial space algorithm
- Reduce my problem to a QBF formula
- 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.
Solution
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.
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.
Context
StackExchange Computer Science Q#141459, answer score: 5
Revisions (0)
No revisions yet.