Let \mathbf{TISP}[T, S], \mathbf{BPTISP}[T, S], \mathbf{NTISP}[T, S] and \mathbf{coNTISP}[T, S] be the set of languages recognized by deterministic, randomized, nondeterministic, and co-nondeterministic algorithms, respectively, running in time T and space S. Let \mathbf{ITIME}[T_V, T_P] be the set of languages recognized by an interactive protocol where the verifier runs in time T_V and the prover runs in time T_P.
For S = \Omega(\log(n)) and T constructible in time \log(T) S + n, we prove:
Fixed a slight bug in the claimed performance of the nondeterministic protocol case. We claimed the verifier ran in time
log(T)^2 S + n
but only showed a verifier which ran in time
log(T)^2 S + log(T) n.
This can be a large difference for NSPACE[n^{1/3}]. I have now updated the paper to prove the stronger claim. This required updating the arithemtization to include a more space efficient, but less time efficient variation, and requires using a second interactive protocol for nondeterministic algorithms to avoid calculating M^ directly with a large field.
I also added an efficient arithmetization of multitape Turing Machines to the appendix. This is (by constant factors) less efficient than arithmetizing the RAM algorithm directly, but the simpler instruction set allows a more complete proof than provided for RAM algorithms. This is probably what I should have used in the main paper, if I would have proved it earlier.
Let \mathbf{TISP}[T, S], \mathbf{BPTISP}[T, S], \mathbf{NTISP}[T, S] and \mathbf{coNTISP}[T, S] be the set of languages recognized by deterministic, randomized, nondeterministic, and co-nondeterministic algorithms, respectively, running in time T and space S. Let \mathbf{ITIME}[T_V, T_P] be the set of languages recognized by an interactive protocol where the verifier runs in time T_V and the prover runs in time T_P.
For S = \Omega(\log(n)) and T constructible in time \log(T) S + n, we prove:
Added abstract back to ECCC, fixed some typos.
Let \mathbf{TISP}[T, S], \mathbf{BPTISP}[T, S], \mathbf{NTISP}[T, S], and \mathbf{CoNTISP}[T, S] be the set of languages recognized by deterministic, randomized, nondeterminsitic, and co-nondeterministic algorithms, respectively, running in time T and space S. Let \mathbf{ITIME}[T_V] be the set of languages recognized by an interactive protocol where the verifier runs in time T_V. We prove:
Added a reference to Thaler's work: "Time-Optimal Interactive Proofs for Circuit Evaluation", which includes the same protocol for repeated matrix squaring. That work however did not apply it to bounded space computation, so our work still seems novel.
Let \mathbf{TISP}[T, S], \mathbf{BPTISP}[T, S], \mathbf{NTISP}[T, S] and \mathbf{coNTISP}[T, S] be the set of languages recognized by deterministic, randomized, nondeterministic, and co-non\-det\-er\-min\-is\-tic algorithms, respectively, running in time T and space S. Let \mathbf{ITIME}[T_V, T_P] be the set of languages recognized by an interactive protocol where the verifier runs in time T_V and the prover runs in time T_P.
For S = \Omega(\log(n)) and T constructible in time \log(T) S + n, we prove:
Near total rewrite of the paper to improve presentation and strengthen the prior results. The results and protocol are unchanged, only the presentation and comparisons with other work. A few notable changes.
1. Updated Shamir's previous protocol to be based on the bounded space variation, and not Shen's modification as it was previously.
2. Added a more detailed explanation for arithmetization and moved it out of preliminaries.
3. Paper no longer assumes reader knows sum check and includes a proof of sum check.
4. Greatly expanded proof idea to give more details.
5. More modular proof, proving the protocol in smaller lemmas instead of all at once.
6. Added a table of different interactive protocols for easy comparison.
7. Added more emphasis to the low space setting, where my protocol has a more clear advantage over Shamir's.
8. Updated preliminaries to include a more formal definition of computation path.
9. Many other spelling and grammatical fixes, and much, much more.
Let \mathbf{TISP}[T, S], \mathbf{BPTISP}[T, S], \mathbf{NTISP}[T, S], and \mathbf{CoNTISP}[T, S] be the set of languages recognized by deterministic, randomized, nondeterminsitic, and co-nondeterministic algorithms, respectively, running in time T and space S. Let \mathbf{ITIME}[T_V] be the set of languages recognized by an interactive protocol where the verifier runs in time T_V. We prove:
