Parity, circuits, and the polynomial-time hierarchy View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

1984-12

AUTHORS

Merrick Furst, James B. Saxe, Michael Sipser

ABSTRACT

A super-polynomial lower bound is given for the size of circuits of fixed depth computing the parity function. Introducing the notion of polynomial-size, constant-depth reduction, similar results are shown for the majority, multiplication, and transitive closure functions. Connections are given to the theory of programmable logic arrays and to the relativization of the polynomial-time hierarchy. More... »

PAGES

13-27

References to SciGraph publications

  • 1976-12. Relativization of questions about log space computability in MATHEMATICAL SYSTEMS THEORY
  • Identifiers

    URI

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

    DOI

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

    DIMENSIONS

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


    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/0101", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Pure Mathematics", 
            "type": "DefinedTerm"
          }, 
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/01", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Mathematical Sciences", 
            "type": "DefinedTerm"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "Carnegie Mellon University", 
              "id": "https://www.grid.ac/institutes/grid.147455.6", 
              "name": [
                "Department of Computer Science, Carnegie-Mellon University, 15213, Pittsburgh, Pa., USA"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Furst", 
            "givenName": "Merrick", 
            "id": "sg:person.0621550627.92", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0621550627.92"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Carnegie Mellon University", 
              "id": "https://www.grid.ac/institutes/grid.147455.6", 
              "name": [
                "Department of Computer Science, Carnegie-Mellon University, 15213, Pittsburgh, Pa., USA"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Saxe", 
            "givenName": "James B.", 
            "id": "sg:person.016640143533.89", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016640143533.89"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Massachusetts Institute of Technology", 
              "id": "https://www.grid.ac/institutes/grid.116068.8", 
              "name": [
                "Department of Mathematics, Massachusetts Institute of Technology, 02139, Boston, Mass., USA"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Sipser", 
            "givenName": "Michael", 
            "id": "sg:person.01352114470.64", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01352114470.64"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "https://doi.org/10.1016/0304-3975(80)90027-4", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1006781257"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0304-3975(80)90074-2", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1015773555"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/322234.322243", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1021206590"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0304-3975(79)90043-4", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1028600948"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf01683260", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1039984490", 
              "https://doi.org/10.1007/bf01683260"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf01683260", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1039984490", 
              "https://doi.org/10.1007/bf01683260"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0304-3975(76)90061-x", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1048647089"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/0204037", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062841277"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "1984-12", 
        "datePublishedReg": "1984-12-01", 
        "description": "A super-polynomial lower bound is given for the size of circuits of fixed depth computing the parity function. Introducing the notion of polynomial-size, constant-depth reduction, similar results are shown for the majority, multiplication, and transitive closure functions. Connections are given to the theory of programmable logic arrays and to the relativization of the polynomial-time hierarchy.", 
        "genre": "research_article", 
        "id": "sg:pub.10.1007/bf01744431", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": false, 
        "isPartOf": [
          {
            "id": "sg:journal.1317508", 
            "issn": [
              "0025-5661"
            ], 
            "name": "Mathematical Systems Theory", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "1", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "17"
          }
        ], 
        "name": "Parity, circuits, and the polynomial-time hierarchy", 
        "pagination": "13-27", 
        "productId": [
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "36a5512624762aad0c75d321d2ecfe05bc4e6aad070e821f6d019cd083178d05"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/bf01744431"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1011469743"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/bf01744431", 
          "https://app.dimensions.ai/details/publication/pub.1011469743"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2019-04-11T10:02", 
        "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
        "sdPublisher": {
          "name": "Springer Nature - SN SciGraph project", 
          "type": "Organization"
        }, 
        "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000347_0000000347/records_89822_00000000.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "http://link.springer.com/10.1007/BF01744431"
      }
    ]
     

    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/bf01744431'

    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/bf01744431'

    Turtle is a human-readable linked data format.

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

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

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


     

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

    99 TRIPLES      21 PREDICATES      34 URIs      19 LITERALS      7 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/bf01744431 schema:about anzsrc-for:01
    2 anzsrc-for:0101
    3 schema:author N027fe4fff2894921b60343c57d4ecc71
    4 schema:citation sg:pub.10.1007/bf01683260
    5 https://doi.org/10.1016/0304-3975(76)90061-x
    6 https://doi.org/10.1016/0304-3975(79)90043-4
    7 https://doi.org/10.1016/0304-3975(80)90027-4
    8 https://doi.org/10.1016/0304-3975(80)90074-2
    9 https://doi.org/10.1137/0204037
    10 https://doi.org/10.1145/322234.322243
    11 schema:datePublished 1984-12
    12 schema:datePublishedReg 1984-12-01
    13 schema:description A super-polynomial lower bound is given for the size of circuits of fixed depth computing the parity function. Introducing the notion of polynomial-size, constant-depth reduction, similar results are shown for the majority, multiplication, and transitive closure functions. Connections are given to the theory of programmable logic arrays and to the relativization of the polynomial-time hierarchy.
    14 schema:genre research_article
    15 schema:inLanguage en
    16 schema:isAccessibleForFree false
    17 schema:isPartOf N10d9b6dd96ff40e8ae127fbbc6b4468d
    18 Nfc777d00895944fab3ca71174aed96ca
    19 sg:journal.1317508
    20 schema:name Parity, circuits, and the polynomial-time hierarchy
    21 schema:pagination 13-27
    22 schema:productId N931e545a004e487d904688d87b5be6f6
    23 Nee61fde3fd9f47988a3f19bc7486cd6e
    24 Nf7d54665ef2e438f916dbb783f8bf560
    25 schema:sameAs https://app.dimensions.ai/details/publication/pub.1011469743
    26 https://doi.org/10.1007/bf01744431
    27 schema:sdDatePublished 2019-04-11T10:02
    28 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    29 schema:sdPublisher N0503fe469d59462eac4c34e07530103e
    30 schema:url http://link.springer.com/10.1007/BF01744431
    31 sgo:license sg:explorer/license/
    32 sgo:sdDataset articles
    33 rdf:type schema:ScholarlyArticle
    34 N027fe4fff2894921b60343c57d4ecc71 rdf:first sg:person.0621550627.92
    35 rdf:rest N7880142fd6fd4b18ba45405714250ee4
    36 N0503fe469d59462eac4c34e07530103e schema:name Springer Nature - SN SciGraph project
    37 rdf:type schema:Organization
    38 N10d9b6dd96ff40e8ae127fbbc6b4468d schema:issueNumber 1
    39 rdf:type schema:PublicationIssue
    40 N315ac3c2190b4a25baabac116991d0c7 rdf:first sg:person.01352114470.64
    41 rdf:rest rdf:nil
    42 N7880142fd6fd4b18ba45405714250ee4 rdf:first sg:person.016640143533.89
    43 rdf:rest N315ac3c2190b4a25baabac116991d0c7
    44 N931e545a004e487d904688d87b5be6f6 schema:name doi
    45 schema:value 10.1007/bf01744431
    46 rdf:type schema:PropertyValue
    47 Nee61fde3fd9f47988a3f19bc7486cd6e schema:name dimensions_id
    48 schema:value pub.1011469743
    49 rdf:type schema:PropertyValue
    50 Nf7d54665ef2e438f916dbb783f8bf560 schema:name readcube_id
    51 schema:value 36a5512624762aad0c75d321d2ecfe05bc4e6aad070e821f6d019cd083178d05
    52 rdf:type schema:PropertyValue
    53 Nfc777d00895944fab3ca71174aed96ca schema:volumeNumber 17
    54 rdf:type schema:PublicationVolume
    55 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
    56 schema:name Mathematical Sciences
    57 rdf:type schema:DefinedTerm
    58 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
    59 schema:name Pure Mathematics
    60 rdf:type schema:DefinedTerm
    61 sg:journal.1317508 schema:issn 0025-5661
    62 schema:name Mathematical Systems Theory
    63 rdf:type schema:Periodical
    64 sg:person.01352114470.64 schema:affiliation https://www.grid.ac/institutes/grid.116068.8
    65 schema:familyName Sipser
    66 schema:givenName Michael
    67 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01352114470.64
    68 rdf:type schema:Person
    69 sg:person.016640143533.89 schema:affiliation https://www.grid.ac/institutes/grid.147455.6
    70 schema:familyName Saxe
    71 schema:givenName James B.
    72 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016640143533.89
    73 rdf:type schema:Person
    74 sg:person.0621550627.92 schema:affiliation https://www.grid.ac/institutes/grid.147455.6
    75 schema:familyName Furst
    76 schema:givenName Merrick
    77 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0621550627.92
    78 rdf:type schema:Person
    79 sg:pub.10.1007/bf01683260 schema:sameAs https://app.dimensions.ai/details/publication/pub.1039984490
    80 https://doi.org/10.1007/bf01683260
    81 rdf:type schema:CreativeWork
    82 https://doi.org/10.1016/0304-3975(76)90061-x schema:sameAs https://app.dimensions.ai/details/publication/pub.1048647089
    83 rdf:type schema:CreativeWork
    84 https://doi.org/10.1016/0304-3975(79)90043-4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1028600948
    85 rdf:type schema:CreativeWork
    86 https://doi.org/10.1016/0304-3975(80)90027-4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1006781257
    87 rdf:type schema:CreativeWork
    88 https://doi.org/10.1016/0304-3975(80)90074-2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1015773555
    89 rdf:type schema:CreativeWork
    90 https://doi.org/10.1137/0204037 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062841277
    91 rdf:type schema:CreativeWork
    92 https://doi.org/10.1145/322234.322243 schema:sameAs https://app.dimensions.ai/details/publication/pub.1021206590
    93 rdf:type schema:CreativeWork
    94 https://www.grid.ac/institutes/grid.116068.8 schema:alternateName Massachusetts Institute of Technology
    95 schema:name Department of Mathematics, Massachusetts Institute of Technology, 02139, Boston, Mass., USA
    96 rdf:type schema:Organization
    97 https://www.grid.ac/institutes/grid.147455.6 schema:alternateName Carnegie Mellon University
    98 schema:name Department of Computer Science, Carnegie-Mellon University, 15213, Pittsburgh, Pa., USA
    99 rdf:type schema:Organization
     




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


    ...