Efficient checking of computations
RJ Lipton - Annual Symposium on Theoretical Aspects of …, 1990 - Springer
RJ Lipton
Annual Symposium on Theoretical Aspects of Computer Science, 1990•SpringerWe show how to efficiently check computations using only logspace even if they are only
given once. This result implies that a polynomial-time verifier can also be restricted to be
logspace with essentially no loss in performance. We also use this result to show that every
set in NP is equal to h (L) where h is a homomorphism and L is accepted by a one-way
probabilistic logspace machine.
given once. This result implies that a polynomial-time verifier can also be restricted to be
logspace with essentially no loss in performance. We also use this result to show that every
set in NP is equal to h (L) where h is a homomorphism and L is accepted by a one-way
probabilistic logspace machine.
Abstract
We show how to efficiently check computations using only logspace even if they are only given once. This result implies that a polynomial-time verifier can also be restricted to be logspace with essentially no loss in performance. We also use this result to show that every set in N P is equal to h(L) where h is a homomorphism and L is accepted by a one-way probabilistic logspace machine.
Springer