Non-deterministic exponential time has two-prover interactive protocols View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

1991-03

AUTHORS

László Babai, Lance Fortnow, Carsten Lund

ABSTRACT

We determine the exact power of two-prover interactive proof systems introduced by Ben-Or, Goldwasser, Kilian, and Wigderson (1988). In this system, two all-powerful noncommunicating provers convince a randomizing polynomial time verifier in polynomial time that the inputx belongs to the languageL. We show that the class of languages having tow-prover interactive proof systems is nondeterministic exponential time.We also show that to prove membership in languages inEXP, the honest provers need the power ofEXP only.The first part of the proof of the main result extends recent techniques of polynomial extrapolation used in the single prover case by Lund, Fortnow, Karloff, Nisan, and Shamir.The second part is averification scheme for multilinearity of a function in several variables held by an oracle and can be viewed as an independent result onprogram verification. Its proof rests on combinatorial techniques employing a simple isoperimetric inequality for certain graphs: More... »

PAGES

3-40

References to SciGraph publications

  • 1991-03. Arithmetization: A new method in structural complexity theory in COMPUTATIONAL COMPLEXITY
  • 1990. Hiding instances in multioracle queries in STACS 90
  • 1983. Complexity classes of alternating machines with oracles in AUTOMATA, LANGUAGES AND PROGRAMMING
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/bf01200056

    DOI

    http://dx.doi.org/10.1007/bf01200056

    DIMENSIONS

    https://app.dimensions.ai/details/publication/pub.1036331166


    Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
    Incoming Citations Browse incoming citations for this publication using opencitations.net

    JSON-LD is the canonical representation for SciGraph data.

    TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

    [
      {
        "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
        "about": [
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Information and Computing Sciences", 
            "type": "DefinedTerm"
          }, 
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0802", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Computation Theory and Mathematics", 
            "type": "DefinedTerm"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "E\u00f6tv\u00f6s University, Budapest, Hungary", 
              "id": "http://www.grid.ac/institutes/grid.5591.8", 
              "name": [
                "University of Chicago, 60637, Chicago, IL", 
                "E\u00f6tv\u00f6s University, Budapest, Hungary"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Babai", 
            "givenName": "L\u00e1szl\u00f3", 
            "id": "sg:person.01061017434.42", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01061017434.42"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Department of Computer Science, University of Chicago, 1100 E. 58th St., 60637, Chicago, IL", 
              "id": "http://www.grid.ac/institutes/grid.170205.1", 
              "name": [
                "Department of Computer Science, University of Chicago, 1100 E. 58th St., 60637, Chicago, IL"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Fortnow", 
            "givenName": "Lance", 
            "id": "sg:person.01210040632.29", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01210040632.29"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Department of Computer Science, University of Chicago, 1100 E. 58th St., 60637, Chicago, IL", 
              "id": "http://www.grid.ac/institutes/grid.170205.1", 
              "name": [
                "Department of Computer Science, University of Chicago, 1100 E. 58th St., 60637, Chicago, IL"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Lund", 
            "givenName": "Carsten", 
            "id": "sg:person.013502474767.02", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013502474767.02"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/3-540-52282-4_30", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1018330720", 
              "https://doi.org/10.1007/3-540-52282-4_30"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bfb0036938", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1043257448", 
              "https://doi.org/10.1007/bfb0036938"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf01200057", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1039532428", 
              "https://doi.org/10.1007/bf01200057"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "1991-03", 
        "datePublishedReg": "1991-03-01", 
        "description": "We determine the exact power of two-prover interactive proof systems introduced by Ben-Or, Goldwasser, Kilian, and Wigderson (1988). In this system, two all-powerful noncommunicating provers convince a randomizing polynomial time verifier in polynomial time that the inputx belongs to the languageL. We show that the class of languages having tow-prover interactive proof systems is nondeterministic exponential time.We also show that to prove membership in languages inEXP, the honest provers need the power ofEXP only.The first part of the proof of the main result extends recent techniques of polynomial extrapolation used in the single prover case by Lund, Fortnow, Karloff, Nisan, and Shamir.The second part is averification scheme for multilinearity of a function in several variables held by an oracle and can be viewed as an independent result onprogram verification. Its proof rests on combinatorial techniques employing a simple isoperimetric inequality for certain graphs:", 
        "genre": "article", 
        "id": "sg:pub.10.1007/bf01200056", 
        "isAccessibleForFree": false, 
        "isPartOf": [
          {
            "id": "sg:journal.1136224", 
            "issn": [
              "1016-3328", 
              "1420-8954"
            ], 
            "name": "computational complexity", 
            "publisher": "Springer Nature", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "1", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "1"
          }
        ], 
        "keywords": [
          "interactive proof systems", 
          "proof system", 
          "polynomial-time verifier", 
          "exponential time", 
          "non-deterministic exponential time", 
          "interactive protocol", 
          "polynomial time", 
          "Ben-Or", 
          "honest provers", 
          "class of languages", 
          "provers", 
          "nondeterministic exponential time", 
          "recent techniques", 
          "combinatorial techniques", 
          "verifier", 
          "Goldwasser", 
          "certain graphs", 
          "Shamir", 
          "inputx", 
          "oracle", 
          "INEXP", 
          "system", 
          "graph", 
          "Fortnow", 
          "verification", 
          "proof", 
          "Wigderson", 
          "polynomial extrapolation", 
          "language", 
          "scheme", 
          "Kilian", 
          "technique", 
          "exact power", 
          "Karloff", 
          "protocol", 
          "Nisan", 
          "time", 
          "multilinearity", 
          "first part", 
          "second part", 
          "part", 
          "class", 
          "power", 
          "membership", 
          "results", 
          "main results", 
          "function", 
          "variables", 
          "cases", 
          "extrapolation", 
          "inequality", 
          "isoperimetric inequality", 
          "Lund", 
          "tows"
        ], 
        "name": "Non-deterministic exponential time has two-prover interactive protocols", 
        "pagination": "3-40", 
        "productId": [
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1036331166"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/bf01200056"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/bf01200056", 
          "https://app.dimensions.ai/details/publication/pub.1036331166"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2022-11-24T20:47", 
        "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
        "sdPublisher": {
          "name": "Springer Nature - SN SciGraph project", 
          "type": "Organization"
        }, 
        "sdSource": "s3://com-springernature-scigraph/baseset/20221124/entities/gbq_results/article/article_256.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "https://doi.org/10.1007/bf01200056"
      }
    ]
     

    Download the RDF metadata as:  json-ld nt turtle xml License info

    HOW TO GET THIS DATA PROGRAMMATICALLY:

    JSON-LD is a popular format for linked data which is fully compatible with JSON.

    curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/bf01200056'

    N-Triples is a line-based linked data format ideal for batch operations.

    curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/bf01200056'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/bf01200056'

    RDF/XML is a standard XML format for linked data.

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/bf01200056'


     

    This table displays all metadata directly associated to this object as RDF triples.

    141 TRIPLES      21 PREDICATES      82 URIs      71 LITERALS      6 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/bf01200056 schema:about anzsrc-for:08
    2 anzsrc-for:0802
    3 schema:author N2fd76e0d5248481e99a60cc6e0db6525
    4 schema:citation sg:pub.10.1007/3-540-52282-4_30
    5 sg:pub.10.1007/bf01200057
    6 sg:pub.10.1007/bfb0036938
    7 schema:datePublished 1991-03
    8 schema:datePublishedReg 1991-03-01
    9 schema:description We determine the exact power of two-prover interactive proof systems introduced by Ben-Or, Goldwasser, Kilian, and Wigderson (1988). In this system, two all-powerful noncommunicating provers convince a randomizing polynomial time verifier in polynomial time that the inputx belongs to the languageL. We show that the class of languages having tow-prover interactive proof systems is nondeterministic exponential time.We also show that to prove membership in languages inEXP, the honest provers need the power ofEXP only.The first part of the proof of the main result extends recent techniques of polynomial extrapolation used in the single prover case by Lund, Fortnow, Karloff, Nisan, and Shamir.The second part is averification scheme for multilinearity of a function in several variables held by an oracle and can be viewed as an independent result onprogram verification. Its proof rests on combinatorial techniques employing a simple isoperimetric inequality for certain graphs:
    10 schema:genre article
    11 schema:isAccessibleForFree false
    12 schema:isPartOf N58543116ce354833ab54ec3f6d259bd5
    13 Ne78ae2baf2e746129f392a698b0f9992
    14 sg:journal.1136224
    15 schema:keywords Ben-Or
    16 Fortnow
    17 Goldwasser
    18 INEXP
    19 Karloff
    20 Kilian
    21 Lund
    22 Nisan
    23 Shamir
    24 Wigderson
    25 cases
    26 certain graphs
    27 class
    28 class of languages
    29 combinatorial techniques
    30 exact power
    31 exponential time
    32 extrapolation
    33 first part
    34 function
    35 graph
    36 honest provers
    37 inequality
    38 inputx
    39 interactive proof systems
    40 interactive protocol
    41 isoperimetric inequality
    42 language
    43 main results
    44 membership
    45 multilinearity
    46 non-deterministic exponential time
    47 nondeterministic exponential time
    48 oracle
    49 part
    50 polynomial extrapolation
    51 polynomial time
    52 polynomial-time verifier
    53 power
    54 proof
    55 proof system
    56 protocol
    57 provers
    58 recent techniques
    59 results
    60 scheme
    61 second part
    62 system
    63 technique
    64 time
    65 tows
    66 variables
    67 verification
    68 verifier
    69 schema:name Non-deterministic exponential time has two-prover interactive protocols
    70 schema:pagination 3-40
    71 schema:productId Na82ced14661249cd81f9004547c4548c
    72 Nd4944e13a60744d2887de0125e31c8fd
    73 schema:sameAs https://app.dimensions.ai/details/publication/pub.1036331166
    74 https://doi.org/10.1007/bf01200056
    75 schema:sdDatePublished 2022-11-24T20:47
    76 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    77 schema:sdPublisher N25e51aa9f21e4b90a3a129fda40a4387
    78 schema:url https://doi.org/10.1007/bf01200056
    79 sgo:license sg:explorer/license/
    80 sgo:sdDataset articles
    81 rdf:type schema:ScholarlyArticle
    82 N25e51aa9f21e4b90a3a129fda40a4387 schema:name Springer Nature - SN SciGraph project
    83 rdf:type schema:Organization
    84 N2fd76e0d5248481e99a60cc6e0db6525 rdf:first sg:person.01061017434.42
    85 rdf:rest N3cc5432758194a12976c0c2d7d4151c2
    86 N3cc5432758194a12976c0c2d7d4151c2 rdf:first sg:person.01210040632.29
    87 rdf:rest N8803f916b64641c78a6469dde465fe2a
    88 N58543116ce354833ab54ec3f6d259bd5 schema:volumeNumber 1
    89 rdf:type schema:PublicationVolume
    90 N8803f916b64641c78a6469dde465fe2a rdf:first sg:person.013502474767.02
    91 rdf:rest rdf:nil
    92 Na82ced14661249cd81f9004547c4548c schema:name dimensions_id
    93 schema:value pub.1036331166
    94 rdf:type schema:PropertyValue
    95 Nd4944e13a60744d2887de0125e31c8fd schema:name doi
    96 schema:value 10.1007/bf01200056
    97 rdf:type schema:PropertyValue
    98 Ne78ae2baf2e746129f392a698b0f9992 schema:issueNumber 1
    99 rdf:type schema:PublicationIssue
    100 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    101 schema:name Information and Computing Sciences
    102 rdf:type schema:DefinedTerm
    103 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
    104 schema:name Computation Theory and Mathematics
    105 rdf:type schema:DefinedTerm
    106 sg:journal.1136224 schema:issn 1016-3328
    107 1420-8954
    108 schema:name computational complexity
    109 schema:publisher Springer Nature
    110 rdf:type schema:Periodical
    111 sg:person.01061017434.42 schema:affiliation grid-institutes:grid.5591.8
    112 schema:familyName Babai
    113 schema:givenName László
    114 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01061017434.42
    115 rdf:type schema:Person
    116 sg:person.01210040632.29 schema:affiliation grid-institutes:grid.170205.1
    117 schema:familyName Fortnow
    118 schema:givenName Lance
    119 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01210040632.29
    120 rdf:type schema:Person
    121 sg:person.013502474767.02 schema:affiliation grid-institutes:grid.170205.1
    122 schema:familyName Lund
    123 schema:givenName Carsten
    124 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013502474767.02
    125 rdf:type schema:Person
    126 sg:pub.10.1007/3-540-52282-4_30 schema:sameAs https://app.dimensions.ai/details/publication/pub.1018330720
    127 https://doi.org/10.1007/3-540-52282-4_30
    128 rdf:type schema:CreativeWork
    129 sg:pub.10.1007/bf01200057 schema:sameAs https://app.dimensions.ai/details/publication/pub.1039532428
    130 https://doi.org/10.1007/bf01200057
    131 rdf:type schema:CreativeWork
    132 sg:pub.10.1007/bfb0036938 schema:sameAs https://app.dimensions.ai/details/publication/pub.1043257448
    133 https://doi.org/10.1007/bfb0036938
    134 rdf:type schema:CreativeWork
    135 grid-institutes:grid.170205.1 schema:alternateName Department of Computer Science, University of Chicago, 1100 E. 58th St., 60637, Chicago, IL
    136 schema:name Department of Computer Science, University of Chicago, 1100 E. 58th St., 60637, Chicago, IL
    137 rdf:type schema:Organization
    138 grid-institutes:grid.5591.8 schema:alternateName Eötvös University, Budapest, Hungary
    139 schema:name Eötvös University, Budapest, Hungary
    140 University of Chicago, 60637, Chicago, IL
    141 rdf:type schema:Organization
     




    Preview window. Press ESC to close (or click here)


    ...