The Informational Content of Canonical Disjoint NP-Pairs View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2007

AUTHORS

Christian Glaßer , Alan L. Selman , Liyu Zhang

ABSTRACT

We investigate the connection between propositional proof systems and their canonical pairs. It is known that simulations between proof systems translate to reductions between their canonical pairs. We focus on the opposite direction and study the following questions. Q1: Where does the implication hold, and where does it fail?Q2: Where can we find proof systems of different strengths, but equivalent canonical pairs?Q3: What do (non-)equivalent canonical pairs tell about the corresponding proof systems?Q4: Is every NP-pair (A,B), where A is NP-complete, strongly many-one equivalent to the canonical pair of some proof system? In short, we show that both parts of Q1 and Q2 can be answered with ‘everywhere’, which generalize previous results by Pudlák and Beyersdorff. Regarding Q3, inequivalent canonical pairs tell that the proof systems are not “very similar”, while equivalent, P-inseparable canonical pairs tell that they are not “very different”. We can relate Q4 to the open problem in structural complexity that asks whether unions of disjoint NP-complete sets are NP-complete. This demonstrates a new connection between proof systems, disjoint NP-pairs, and unions of disjoint NP-complete sets. Q1: Where does the implication hold, and where does it fail? Q2: Where can we find proof systems of different strengths, but equivalent canonical pairs? Q3: What do (non-)equivalent canonical pairs tell about the corresponding proof systems? Q4: Is every NP-pair (A,B), where A is NP-complete, strongly many-one equivalent to the canonical pair of some proof system? More... »

PAGES

307-317

References to SciGraph publications

  • 2006. Disjoint NP-Pairs from Propositional Proof Systems in THEORY AND APPLICATIONS OF MODELS OF COMPUTATION
  • 2006. Survey of Disjoint NP-pairs and Relations to Propositional Proof Systems in THEORETICAL COMPUTER SCIENCE
  • 2007. The Complexity of Unions of Disjoint Sets in STACS 2007
  • Book

    TITLE

    Computing and Combinatorics

    ISBN

    978-3-540-73544-1
    978-3-540-73545-8

    Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/978-3-540-73545-8_31

    DOI

    http://dx.doi.org/10.1007/978-3-540-73545-8_31

    DIMENSIONS

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


    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/0802", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Computation Theory and Mathematics", 
            "type": "DefinedTerm"
          }, 
          {
            "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"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "University of W\u00fcrzburg", 
              "id": "https://www.grid.ac/institutes/grid.8379.5", 
              "name": [
                "Lehrstuhl f\u00fcr Informatik IV, Universit\u00e4t W\u00fcrzburg, Am Hubland, 97074 W\u00fcrzburg, Germany"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Gla\u00dfer", 
            "givenName": "Christian", 
            "id": "sg:person.010502766006.46", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010502766006.46"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "University at Buffalo, State University of New York", 
              "id": "https://www.grid.ac/institutes/grid.273335.3", 
              "name": [
                "Department of Computer Science and Engineering, University at Buffalo, Buffalo, NY 14260"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Selman", 
            "givenName": "Alan L.", 
            "id": "sg:person.01304131654.08", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01304131654.08"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "University at Buffalo, State University of New York", 
              "id": "https://www.grid.ac/institutes/grid.273335.3", 
              "name": [
                "Department of Computer Science and Engineering, University at Buffalo, Buffalo, NY 14260"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Zhang", 
            "givenName": "Liyu", 
            "id": "sg:person.07730202641.57", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07730202641.57"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "https://doi.org/10.1016/s0304-3975(02)00411-5", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1003761173"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/s0304-3975(02)00411-5", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1003761173"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-70918-3_22", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1004155255", 
              "https://doi.org/10.1007/978-3-540-70918-3_22"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/s0890-5401(03)00058-0", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1009300655"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/s0890-5401(03)00058-0", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1009300655"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.tcs.2006.10.006", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1014095401"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11750321_23", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1017080820", 
              "https://doi.org/10.1007/11750321_23"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11750321_23", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1017080820", 
              "https://doi.org/10.1007/11750321_23"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0022-0000(92)90023-c", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1018733875"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11685654_11", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1040939639", 
              "https://doi.org/10.1007/11685654_11"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11685654_11", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1040939639", 
              "https://doi.org/10.1007/11685654_11"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.2307/2273702", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1043663701"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/0217018", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062842037"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/s0097539703425848", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062879437"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/s009753970444421x", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062879543"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2007", 
        "datePublishedReg": "2007-01-01", 
        "description": "We investigate the connection between propositional proof systems and their canonical pairs. It is known that simulations between proof systems translate to reductions between their canonical pairs. We focus on the opposite direction and study the following questions. Q1: Where does the implication hold, and where does it fail?Q2: Where can we find proof systems of different strengths, but equivalent canonical pairs?Q3: What do (non-)equivalent canonical pairs tell about the corresponding proof systems?Q4: Is every NP-pair (A,B), where A is NP-complete, strongly many-one equivalent to the canonical pair of some proof system? In short, we show that both parts of Q1 and Q2 can be answered with \u2018everywhere\u2019, which generalize previous results by Pudl\u00e1k and Beyersdorff. Regarding Q3, inequivalent canonical pairs tell that the proof systems are not \u201cvery similar\u201d, while equivalent, P-inseparable canonical pairs tell that they are not \u201cvery different\u201d. We can relate Q4 to the open problem in structural complexity that asks whether unions of disjoint NP-complete sets are NP-complete. This demonstrates a new connection between proof systems, disjoint NP-pairs, and unions of disjoint NP-complete sets. Q1: Where does the implication hold, and where does it fail? Q2: Where can we find proof systems of different strengths, but equivalent canonical pairs? Q3: What do (non-)equivalent canonical pairs tell about the corresponding proof systems? Q4: Is every NP-pair (A,B), where A is NP-complete, strongly many-one equivalent to the canonical pair of some proof system?", 
        "editor": [
          {
            "familyName": "Lin", 
            "givenName": "Guohui", 
            "type": "Person"
          }
        ], 
        "genre": "chapter", 
        "id": "sg:pub.10.1007/978-3-540-73545-8_31", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": true, 
        "isPartOf": {
          "isbn": [
            "978-3-540-73544-1", 
            "978-3-540-73545-8"
          ], 
          "name": "Computing and Combinatorics", 
          "type": "Book"
        }, 
        "name": "The Informational Content of Canonical Disjoint NP-Pairs", 
        "pagination": "307-317", 
        "productId": [
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/978-3-540-73545-8_31"
            ]
          }, 
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "79d5b26d22012336ac7ec49e4b867d4cbd0a8393bfb68db237dd79d61424390e"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1025573823"
            ]
          }
        ], 
        "publisher": {
          "location": "Berlin, Heidelberg", 
          "name": "Springer Berlin Heidelberg", 
          "type": "Organisation"
        }, 
        "sameAs": [
          "https://doi.org/10.1007/978-3-540-73545-8_31", 
          "https://app.dimensions.ai/details/publication/pub.1025573823"
        ], 
        "sdDataset": "chapters", 
        "sdDatePublished": "2019-04-16T05:27", 
        "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/0000000345_0000000345/records_64117_00000001.jsonl", 
        "type": "Chapter", 
        "url": "https://link.springer.com/10.1007%2F978-3-540-73545-8_31"
      }
    ]
     

    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/978-3-540-73545-8_31'

    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/978-3-540-73545-8_31'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-73545-8_31'

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

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-73545-8_31'


     

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

    118 TRIPLES      23 PREDICATES      38 URIs      20 LITERALS      8 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/978-3-540-73545-8_31 schema:about anzsrc-for:08
    2 anzsrc-for:0802
    3 schema:author Nf92b432ce46249c388012fdedbfbd48c
    4 schema:citation sg:pub.10.1007/11685654_11
    5 sg:pub.10.1007/11750321_23
    6 sg:pub.10.1007/978-3-540-70918-3_22
    7 https://doi.org/10.1016/0022-0000(92)90023-c
    8 https://doi.org/10.1016/j.tcs.2006.10.006
    9 https://doi.org/10.1016/s0304-3975(02)00411-5
    10 https://doi.org/10.1016/s0890-5401(03)00058-0
    11 https://doi.org/10.1137/0217018
    12 https://doi.org/10.1137/s0097539703425848
    13 https://doi.org/10.1137/s009753970444421x
    14 https://doi.org/10.2307/2273702
    15 schema:datePublished 2007
    16 schema:datePublishedReg 2007-01-01
    17 schema:description We investigate the connection between propositional proof systems and their canonical pairs. It is known that simulations between proof systems translate to reductions between their canonical pairs. We focus on the opposite direction and study the following questions. Q1: Where does the implication hold, and where does it fail?Q2: Where can we find proof systems of different strengths, but equivalent canonical pairs?Q3: What do (non-)equivalent canonical pairs tell about the corresponding proof systems?Q4: Is every NP-pair (A,B), where A is NP-complete, strongly many-one equivalent to the canonical pair of some proof system? In short, we show that both parts of Q1 and Q2 can be answered with ‘everywhere’, which generalize previous results by Pudlák and Beyersdorff. Regarding Q3, inequivalent canonical pairs tell that the proof systems are not “very similar”, while equivalent, P-inseparable canonical pairs tell that they are not “very different”. We can relate Q4 to the open problem in structural complexity that asks whether unions of disjoint NP-complete sets are NP-complete. This demonstrates a new connection between proof systems, disjoint NP-pairs, and unions of disjoint NP-complete sets. Q1: Where does the implication hold, and where does it fail? Q2: Where can we find proof systems of different strengths, but equivalent canonical pairs? Q3: What do (non-)equivalent canonical pairs tell about the corresponding proof systems? Q4: Is every NP-pair (A,B), where A is NP-complete, strongly many-one equivalent to the canonical pair of some proof system?
    18 schema:editor N72f7b3f79c5841d98df639e29db69d94
    19 schema:genre chapter
    20 schema:inLanguage en
    21 schema:isAccessibleForFree true
    22 schema:isPartOf N78edd5d2b01f42dca99b78b7264e0ed3
    23 schema:name The Informational Content of Canonical Disjoint NP-Pairs
    24 schema:pagination 307-317
    25 schema:productId N0d3b2e5bfbff478faa9ddabbe7195864
    26 N5f13630cb31547e6b5b6a70d7a796017
    27 N9782e2082c0b4143b9d368580583f227
    28 schema:publisher N01fcacf377984dae8138856ac2577492
    29 schema:sameAs https://app.dimensions.ai/details/publication/pub.1025573823
    30 https://doi.org/10.1007/978-3-540-73545-8_31
    31 schema:sdDatePublished 2019-04-16T05:27
    32 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    33 schema:sdPublisher Na166957ec95c4721b948c294d3ee4fac
    34 schema:url https://link.springer.com/10.1007%2F978-3-540-73545-8_31
    35 sgo:license sg:explorer/license/
    36 sgo:sdDataset chapters
    37 rdf:type schema:Chapter
    38 N01fcacf377984dae8138856ac2577492 schema:location Berlin, Heidelberg
    39 schema:name Springer Berlin Heidelberg
    40 rdf:type schema:Organisation
    41 N0d3b2e5bfbff478faa9ddabbe7195864 schema:name readcube_id
    42 schema:value 79d5b26d22012336ac7ec49e4b867d4cbd0a8393bfb68db237dd79d61424390e
    43 rdf:type schema:PropertyValue
    44 N393582f944904f0db1f37ac85df6991e rdf:first sg:person.01304131654.08
    45 rdf:rest N6ab668db9a984ebbadc7cb7cc1259353
    46 N5f13630cb31547e6b5b6a70d7a796017 schema:name doi
    47 schema:value 10.1007/978-3-540-73545-8_31
    48 rdf:type schema:PropertyValue
    49 N6ab668db9a984ebbadc7cb7cc1259353 rdf:first sg:person.07730202641.57
    50 rdf:rest rdf:nil
    51 N72f7b3f79c5841d98df639e29db69d94 rdf:first N89f10af54ff748f1bbba0c2f502a92ac
    52 rdf:rest rdf:nil
    53 N78edd5d2b01f42dca99b78b7264e0ed3 schema:isbn 978-3-540-73544-1
    54 978-3-540-73545-8
    55 schema:name Computing and Combinatorics
    56 rdf:type schema:Book
    57 N89f10af54ff748f1bbba0c2f502a92ac schema:familyName Lin
    58 schema:givenName Guohui
    59 rdf:type schema:Person
    60 N9782e2082c0b4143b9d368580583f227 schema:name dimensions_id
    61 schema:value pub.1025573823
    62 rdf:type schema:PropertyValue
    63 Na166957ec95c4721b948c294d3ee4fac schema:name Springer Nature - SN SciGraph project
    64 rdf:type schema:Organization
    65 Nf92b432ce46249c388012fdedbfbd48c rdf:first sg:person.010502766006.46
    66 rdf:rest N393582f944904f0db1f37ac85df6991e
    67 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    68 schema:name Information and Computing Sciences
    69 rdf:type schema:DefinedTerm
    70 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
    71 schema:name Computation Theory and Mathematics
    72 rdf:type schema:DefinedTerm
    73 sg:person.010502766006.46 schema:affiliation https://www.grid.ac/institutes/grid.8379.5
    74 schema:familyName Glaßer
    75 schema:givenName Christian
    76 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010502766006.46
    77 rdf:type schema:Person
    78 sg:person.01304131654.08 schema:affiliation https://www.grid.ac/institutes/grid.273335.3
    79 schema:familyName Selman
    80 schema:givenName Alan L.
    81 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01304131654.08
    82 rdf:type schema:Person
    83 sg:person.07730202641.57 schema:affiliation https://www.grid.ac/institutes/grid.273335.3
    84 schema:familyName Zhang
    85 schema:givenName Liyu
    86 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07730202641.57
    87 rdf:type schema:Person
    88 sg:pub.10.1007/11685654_11 schema:sameAs https://app.dimensions.ai/details/publication/pub.1040939639
    89 https://doi.org/10.1007/11685654_11
    90 rdf:type schema:CreativeWork
    91 sg:pub.10.1007/11750321_23 schema:sameAs https://app.dimensions.ai/details/publication/pub.1017080820
    92 https://doi.org/10.1007/11750321_23
    93 rdf:type schema:CreativeWork
    94 sg:pub.10.1007/978-3-540-70918-3_22 schema:sameAs https://app.dimensions.ai/details/publication/pub.1004155255
    95 https://doi.org/10.1007/978-3-540-70918-3_22
    96 rdf:type schema:CreativeWork
    97 https://doi.org/10.1016/0022-0000(92)90023-c schema:sameAs https://app.dimensions.ai/details/publication/pub.1018733875
    98 rdf:type schema:CreativeWork
    99 https://doi.org/10.1016/j.tcs.2006.10.006 schema:sameAs https://app.dimensions.ai/details/publication/pub.1014095401
    100 rdf:type schema:CreativeWork
    101 https://doi.org/10.1016/s0304-3975(02)00411-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1003761173
    102 rdf:type schema:CreativeWork
    103 https://doi.org/10.1016/s0890-5401(03)00058-0 schema:sameAs https://app.dimensions.ai/details/publication/pub.1009300655
    104 rdf:type schema:CreativeWork
    105 https://doi.org/10.1137/0217018 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062842037
    106 rdf:type schema:CreativeWork
    107 https://doi.org/10.1137/s0097539703425848 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062879437
    108 rdf:type schema:CreativeWork
    109 https://doi.org/10.1137/s009753970444421x schema:sameAs https://app.dimensions.ai/details/publication/pub.1062879543
    110 rdf:type schema:CreativeWork
    111 https://doi.org/10.2307/2273702 schema:sameAs https://app.dimensions.ai/details/publication/pub.1043663701
    112 rdf:type schema:CreativeWork
    113 https://www.grid.ac/institutes/grid.273335.3 schema:alternateName University at Buffalo, State University of New York
    114 schema:name Department of Computer Science and Engineering, University at Buffalo, Buffalo, NY 14260
    115 rdf:type schema:Organization
    116 https://www.grid.ac/institutes/grid.8379.5 schema:alternateName University of Würzburg
    117 schema:name Lehrstuhl für Informatik IV, Universität Würzburg, Am Hubland, 97074 Würzburg, Germany
    118 rdf:type schema:Organization
     




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


    ...