Abstract
We explore the connection between public-coin interactive proof systems with logspace verifiers and \(\mathcal{N}\mathcal{C}\)using two different approaches. In the first approach, we describe an interactive proof system for accepting any language in \(\mathcal{N}\mathcal{C}\)after a logspace reduction, where the verifier is logspace-bounded and the protocol requires polylog time. These results are proved by describing \(\mathcal{N}\mathcal{C}\)computations as computations over arithmetic circuits using maximum and average gates, and then translating the arithmetic circuits into interactive proof systems in a natural way. In the second approach, we give a characterization of \(\mathcal{N}\mathcal{C}\)in terms of interactive proof systems where the verifier is logspace-bounded and runs in polylog time. The equivalent interactive proof systems work with error-correcting encodings of inputs, using the polylogarithmically checkable codes introduced in the context of transparent proofs.
We also characterize \(\mathcal{N}\mathcal{C}\)and \(\mathcal{P}\mathcal{S}\mathcal{P}\mathcal{A}\mathcal{C}\mathcal{E}\)via public-coin interactive proof systems where the verifier is logspace-bounded, but has restricted access to auxiliary storage.
Work done while the author was with the Institute of Mathematical Sciences, Madras 600 113, India.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
References
L. Babai. Trading group theory for randomness. In Proc. 17th STOC, pp 421–429, 1985.
L. Babai and K. Friedl. On slightly superlinear transparent proofs. Technical Report CS-93-13, Department of Computer Science, University of Chicago, 1993.
L. Babai, L. Fortnow, L.A. Levin, and M. Szegedy. Checking computations in polylogarithmic time. In Proc. 23rd STOC, pp 21–31, 1991.
L. Babai and S. Moran. Arthur-Merlin games: a randomized proof system and a hierarchy of complexity classes. J. Comp. Syst. Sci., 36:254–276, 1988.
A. Condon and R. Ladner. Probabilistic game automata. J. Comp. Syst. Sci., 36(3):452–489, 1988.
A. Condon and R. Lipton. On the complexity of space-bounded interactive proofs. In Proc. 30th FOCS, pp 462–467, 1989.
A. Condon and R. Ladner. Interactive proof systems with polynomially bounded strategies. In Proc. 7th Conference on Structure in Complexity Theory, pp 282–294, 1992.
A. Condon. The complexity of the max word problem and the power of one-way interactive proof systems. In Proc. 8th STACS, pp 456–465, 1991. LNCS 480.
L. Fortnow and C. Lund. Interactive proof systems and alternating timespace complexity. Theoretical Computer Science, 113:55–73, 1993. also in Proc. 8th STACS 1991, LNCS 480.
L. Fortnow. Complexity-theoretic aspects of interactive proof systems. PhD thesis, M. I. T., May 1989. Tech. Rep. MIT/LCS/TR-447.
S. Goldwasser, S. Micali, and C. Rackoff. The knowledge complexity of interactive proof systems. In Proc. 17th STOC, pp 291–304, 1985. full version in SIAM J. Comput., Vol 18(1), pp 186–208.
S. Goldwasser and M. Sipser. Private coins versus public coins in interactive proof systems. In Proc. 18th STOC, 1986. also in Advances in Computing Research 5: Randomness and Computation, JAI Press, Greenwich, CT, 1989.
B. Jenner and B. Kersig. Characterizing the polynomial hierarchy by alternating auxiliary pushdown automata. RAIRO Theoretical Informatics and Applications, 23:93–99, 1989. also in Proc. STACS(1988), LNCS 294 118–125.
C. Lund, L. Fortnow, H. Karloff, and N. Nisan. Algebraic methods for interactive proof systems. J. ACM, 39(4):859–868, October 1992. also in Proc. 31st FOCS 1990, pp 1–10.
R. J. Lipton. Efficient checking of computations. In Proc. 7th STACS, pp 207–215, 1990. LNCS 415.
W.L. Ruzzo. On uniform circuit complexity. J. Comput. Syst. Sci., 22:365–383, 1981.
A. Shamir. IP=PSPACE. J. ACM, 39(4):869–877, 1992. also in Proc. 31st FOCS 1990, pp 11–15.
A. Shen. IP=PSPACE: Simplified proof. J. ACM, 39(4):878–880, 1992.
V. Vinay and V. Chandru. The expressibility of nondeterministic auxiliary stack automata and its relation to treesize bounded alternating auxiliary pushdown automata. In Proc. 10th FST & TCS, pp 104–114, 1990. LNCS 472.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1995 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Lokam, S.V., Mahajan, M., Vinay, V. (1995). Logspace verifiers, NC, and NP. In: Staples, J., Eades, P., Katoh, N., Moffat, A. (eds) Algorithms and Computations. ISAAC 1995. Lecture Notes in Computer Science, vol 1004. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0015408
Download citation
DOI: https://doi.org/10.1007/BFb0015408
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-60573-7
Online ISBN: 978-3-540-47766-2
eBook Packages: Springer Book Archive