• DocumentCode
    1992320
  • Title

    Alternation in interaction

  • Author

    Kiwi, M. ; Lund, C. ; Russell, A. ; Spielman, D. ; Sundaram, R.

  • Author_Institution
    Dept. of Appl. Math., MIT, Cambridge, MA, USA
  • fYear
    1994
  • fDate
    28 Jun- 1 Jul 1994
  • Firstpage
    294
  • Lastpage
    303
  • Abstract
    We study competing-prover one-round interactive proof systems. We show that one-round proof systems in which the first prover is trying to convince a verifier to accept and the second prover is trying to make the verifier reject recognized languages in NEXPTIME, and, with restrictions on communication and randomness, languages in NP. We extended the restricted model to an alternating sequence of k competing provers, which we show characterizes Σk-1P. Alternating oracle proof systems are also examined
  • Keywords
    automata theory; computational complexity; decidability; formal languages; theorem proving; NEXPTIME; alternating sequence; competing-prover one-round interactive proof systems; languages; oracle proof systems; undecidability; Books; Computer science; Contracts; Marine vehicles; Mathematical model; Mathematics; Polynomials; Protocols; Voting;
  • fLanguage
    English
  • Publisher
    ieee
  • Conference_Titel
    Structure in Complexity Theory Conference, 1994., Proceedings of the Ninth Annual
  • Conference_Location
    Amsterdam
  • Print_ISBN
    0-8186-5670-0
  • Type

    conf

  • DOI
    10.1109/SCT.1994.315795
  • Filename
    315795
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=1992320