AND-Compression of NP-Complete Problems: Streamlined Proof and Minor Observations View Full Text


Ontology type: schema:ScholarlyArticle      Open Access: True


Article Info

DATE

2016-06

AUTHORS

Holger Dell

ABSTRACT

Drucker (Proceedings of the 53rd annual symposium on foundations of computer science (FOCS), pp 609–618. doi:10.1109/FOCS.2012.71, 2012) proved the following result: Unless the unlikely complexity-theoretic collapse coNP⊆NP/poly occurs, there is no AND-compression for SAT. The result has implications for the compressibility and kernelizability of a whole range of NP-complete parameterized problems. We present a streamlined proof of Drucker’s theorem. An AND-compression is a deterministic polynomial-time algorithm that maps a set of SAT-instances x1,…,xt to a single SAT-instance y of size poly(maxi|xi|) such that y is satisfiable if and only if all xi are satisfiable. The “AND” in the name stems from the fact that the predicate “y is satisfiable” can be written as the AND of all predicates “xi is satisfiable”. Drucker’s theorem complements the result by Bodlaender et al. (J Comput Syst Sci 75:423–434, 2009) and Fortnow and Santhanam (J Comput Syst Sci 77:91–106, 2011), who proved the analogous statement for OR-compressions, and Drucker’s proof not only subsumes their result but also extends it to randomized compression algorithms that are allowed to have a certain probability of failure. Drucker (Proceedings of the 53rd annual symposium on foundations of computer science (FOCS), pp 609–618. doi:10.1109/FOCS.2012.71, 2012) presented two proofs: The first uses information theory and the minimax theorem from game theory, and the second is an elementary, iterative proof that is not as general. In our proof, we realize the iterative structure as a generalization of the arguments of Ko (J Comput Syst Sci 26:209–211, 1983) for P-selective sets, which use the fact that tournaments have dominating sets of logarithmic size. We generalize this fact to hypergraph tournaments. Our proof achieves the full generality of Drucker’s theorem, avoids the minimax theorem, and restricts the use of information theory to a single, intuitive lemma about the average noise sensitivity of compressive maps. To prove this lemma, we use the same information-theoretic inequalities as Drucker. More... »

PAGES

403-423

References to SciGraph publications

  • 2013-06. Is Valiant–Vazirani’s isolation probability improvable? in COMPUTATIONAL COMPLEXITY
  • 2011. On the Complexity of Computational Problems Regarding Distributions in STUDIES IN COMPLEXITY AND CRYPTOGRAPHY. MISCELLANEA ON THE INTERPLAY BETWEEN RANDOMNESS AND COMPUTATION
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/s00453-015-0110-y

    DOI

    http://dx.doi.org/10.1007/s00453-015-0110-y

    DIMENSIONS

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


    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": "Laboratoire d'Informatique Algorithmique: Fondements et Applications", 
              "id": "https://www.grid.ac/institutes/grid.462842.e", 
              "name": [
                "Cluster of Excellence (MMCI), Saarland University, Saarbr\u00fccken, Germany", 
                "Simons Institute for the Theory of Computing, Berkeley, CA, USA", 
                "UC Berkeley, Berkeley, CA, USA", 
                "LIAFA, Universit\u00e9 Paris Diderot, Paris, France"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Dell", 
            "givenName": "Holger", 
            "id": "sg:person.07535363217.36", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07535363217.36"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "https://doi.org/10.1016/j.jcss.2010.06.007", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1018586756"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s00037-013-0059-7", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1023864625", 
              "https://doi.org/10.1007/s00037-013-0059-7"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/2629620", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1037761533"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0022-0000(83)90013-2", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1038430534"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/636865.636868", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1046390917"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.jcss.2009.04.001", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1046558319"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-22670-0_27", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1050124444", 
              "https://doi.org/10.1007/978-3-642-22670-0_27"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-22670-0_27", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1050124444", 
              "https://doi.org/10.1007/978-3-642-22670-0_27"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/tit.2003.811927", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1061649825"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/060668092", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062849640"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/120880240", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062869534"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/sfcs.1978.37", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1086202543"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/1.9781611973099.10", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1088801430"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/1.9781611973099.6", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1088801524"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/1.9781611973099.9", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1088801559"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/1.9781611973402.116", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1088801809"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/focs.2012.71", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1094542039"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1017/cbo9780511804090", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1098662846"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2016-06", 
        "datePublishedReg": "2016-06-01", 
        "description": "Drucker (Proceedings of the 53rd annual symposium on foundations of computer science (FOCS), pp 609\u2013618. doi:10.1109/FOCS.2012.71, 2012) proved the following result: Unless the unlikely complexity-theoretic collapse coNP\u2286NP/poly occurs, there is no AND-compression for SAT. The result has implications for the compressibility and kernelizability of a whole range of NP-complete parameterized problems. We present a streamlined proof of Drucker\u2019s theorem. An AND-compression is a deterministic polynomial-time algorithm that maps a set of SAT-instances x1,\u2026,xt to a single SAT-instance y of size poly(maxi|xi|) such that y is satisfiable if and only if all xi are satisfiable. The \u201cAND\u201d in the name stems from the fact that the predicate \u201cy is satisfiable\u201d can be written as the AND of all predicates \u201cxi is satisfiable\u201d. Drucker\u2019s theorem complements the result by Bodlaender et al. (J Comput Syst Sci 75:423\u2013434, 2009) and Fortnow and Santhanam (J Comput Syst Sci 77:91\u2013106, 2011), who proved the analogous statement for OR-compressions, and Drucker\u2019s proof not only subsumes their result but also extends it to randomized compression algorithms that are allowed to have a certain probability of failure. Drucker (Proceedings of the 53rd annual symposium on foundations of computer science (FOCS), pp 609\u2013618. doi:10.1109/FOCS.2012.71, 2012) presented two proofs: The first uses information theory and the minimax theorem from game theory, and the second is an elementary, iterative proof that is not as general. In our proof, we realize the iterative structure as a generalization of the arguments of Ko (J Comput Syst Sci 26:209\u2013211, 1983) for P-selective sets, which use the fact that tournaments have dominating sets of logarithmic size. We generalize this fact to hypergraph tournaments. Our proof achieves the full generality of Drucker\u2019s theorem, avoids the minimax theorem, and restricts the use of information theory to a single, intuitive lemma about the average noise sensitivity of compressive maps. To prove this lemma, we use the same information-theoretic inequalities as Drucker.", 
        "genre": "research_article", 
        "id": "sg:pub.10.1007/s00453-015-0110-y", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": true, 
        "isPartOf": [
          {
            "id": "sg:journal.1047644", 
            "issn": [
              "0178-4617", 
              "1432-0541"
            ], 
            "name": "Algorithmica", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "2", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "75"
          }
        ], 
        "name": "AND-Compression of NP-Complete Problems: Streamlined Proof and Minor Observations", 
        "pagination": "403-423", 
        "productId": [
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "0ff4d6c5bf295677b388db35f06db70ee522e4f0897ba2342ee76c5becbb7ef8"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/s00453-015-0110-y"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1003349894"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/s00453-015-0110-y", 
          "https://app.dimensions.ai/details/publication/pub.1003349894"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2019-04-10T15:50", 
        "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/0000000001_0000000264/records_8664_00000510.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "http://link.springer.com/10.1007%2Fs00453-015-0110-y"
      }
    ]
     

    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/s00453-015-0110-y'

    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/s00453-015-0110-y'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00453-015-0110-y'

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

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00453-015-0110-y'


     

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

    117 TRIPLES      21 PREDICATES      44 URIs      19 LITERALS      7 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/s00453-015-0110-y schema:about anzsrc-for:08
    2 anzsrc-for:0802
    3 schema:author Nd5508acee4074616a51dcac45c60bc5d
    4 schema:citation sg:pub.10.1007/978-3-642-22670-0_27
    5 sg:pub.10.1007/s00037-013-0059-7
    6 https://doi.org/10.1016/0022-0000(83)90013-2
    7 https://doi.org/10.1016/j.jcss.2009.04.001
    8 https://doi.org/10.1016/j.jcss.2010.06.007
    9 https://doi.org/10.1017/cbo9780511804090
    10 https://doi.org/10.1109/focs.2012.71
    11 https://doi.org/10.1109/sfcs.1978.37
    12 https://doi.org/10.1109/tit.2003.811927
    13 https://doi.org/10.1137/060668092
    14 https://doi.org/10.1137/1.9781611973099.10
    15 https://doi.org/10.1137/1.9781611973099.6
    16 https://doi.org/10.1137/1.9781611973099.9
    17 https://doi.org/10.1137/1.9781611973402.116
    18 https://doi.org/10.1137/120880240
    19 https://doi.org/10.1145/2629620
    20 https://doi.org/10.1145/636865.636868
    21 schema:datePublished 2016-06
    22 schema:datePublishedReg 2016-06-01
    23 schema:description Drucker (Proceedings of the 53rd annual symposium on foundations of computer science (FOCS), pp 609–618. doi:10.1109/FOCS.2012.71, 2012) proved the following result: Unless the unlikely complexity-theoretic collapse coNP⊆NP/poly occurs, there is no AND-compression for SAT. The result has implications for the compressibility and kernelizability of a whole range of NP-complete parameterized problems. We present a streamlined proof of Drucker’s theorem. An AND-compression is a deterministic polynomial-time algorithm that maps a set of SAT-instances x1,…,xt to a single SAT-instance y of size poly(maxi|xi|) such that y is satisfiable if and only if all xi are satisfiable. The “AND” in the name stems from the fact that the predicate “y is satisfiable” can be written as the AND of all predicates “xi is satisfiable”. Drucker’s theorem complements the result by Bodlaender et al. (J Comput Syst Sci 75:423–434, 2009) and Fortnow and Santhanam (J Comput Syst Sci 77:91–106, 2011), who proved the analogous statement for OR-compressions, and Drucker’s proof not only subsumes their result but also extends it to randomized compression algorithms that are allowed to have a certain probability of failure. Drucker (Proceedings of the 53rd annual symposium on foundations of computer science (FOCS), pp 609–618. doi:10.1109/FOCS.2012.71, 2012) presented two proofs: The first uses information theory and the minimax theorem from game theory, and the second is an elementary, iterative proof that is not as general. In our proof, we realize the iterative structure as a generalization of the arguments of Ko (J Comput Syst Sci 26:209–211, 1983) for P-selective sets, which use the fact that tournaments have dominating sets of logarithmic size. We generalize this fact to hypergraph tournaments. Our proof achieves the full generality of Drucker’s theorem, avoids the minimax theorem, and restricts the use of information theory to a single, intuitive lemma about the average noise sensitivity of compressive maps. To prove this lemma, we use the same information-theoretic inequalities as Drucker.
    24 schema:genre research_article
    25 schema:inLanguage en
    26 schema:isAccessibleForFree true
    27 schema:isPartOf N7962946b95184fde98d97807b0535e01
    28 Na81cceb1311d4ce2ab1228c51d4ac0b1
    29 sg:journal.1047644
    30 schema:name AND-Compression of NP-Complete Problems: Streamlined Proof and Minor Observations
    31 schema:pagination 403-423
    32 schema:productId N281b1c3d540648d08c3184c57ce0e3e4
    33 N339af8b61be144c6952902e34bad526f
    34 Nea2619620afd41318d8a0bea1df7ff2c
    35 schema:sameAs https://app.dimensions.ai/details/publication/pub.1003349894
    36 https://doi.org/10.1007/s00453-015-0110-y
    37 schema:sdDatePublished 2019-04-10T15:50
    38 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    39 schema:sdPublisher Nd32be691ead2420f9f3f8575437fed85
    40 schema:url http://link.springer.com/10.1007%2Fs00453-015-0110-y
    41 sgo:license sg:explorer/license/
    42 sgo:sdDataset articles
    43 rdf:type schema:ScholarlyArticle
    44 N281b1c3d540648d08c3184c57ce0e3e4 schema:name readcube_id
    45 schema:value 0ff4d6c5bf295677b388db35f06db70ee522e4f0897ba2342ee76c5becbb7ef8
    46 rdf:type schema:PropertyValue
    47 N339af8b61be144c6952902e34bad526f schema:name doi
    48 schema:value 10.1007/s00453-015-0110-y
    49 rdf:type schema:PropertyValue
    50 N7962946b95184fde98d97807b0535e01 schema:issueNumber 2
    51 rdf:type schema:PublicationIssue
    52 Na81cceb1311d4ce2ab1228c51d4ac0b1 schema:volumeNumber 75
    53 rdf:type schema:PublicationVolume
    54 Nd32be691ead2420f9f3f8575437fed85 schema:name Springer Nature - SN SciGraph project
    55 rdf:type schema:Organization
    56 Nd5508acee4074616a51dcac45c60bc5d rdf:first sg:person.07535363217.36
    57 rdf:rest rdf:nil
    58 Nea2619620afd41318d8a0bea1df7ff2c schema:name dimensions_id
    59 schema:value pub.1003349894
    60 rdf:type schema:PropertyValue
    61 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    62 schema:name Information and Computing Sciences
    63 rdf:type schema:DefinedTerm
    64 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
    65 schema:name Computation Theory and Mathematics
    66 rdf:type schema:DefinedTerm
    67 sg:journal.1047644 schema:issn 0178-4617
    68 1432-0541
    69 schema:name Algorithmica
    70 rdf:type schema:Periodical
    71 sg:person.07535363217.36 schema:affiliation https://www.grid.ac/institutes/grid.462842.e
    72 schema:familyName Dell
    73 schema:givenName Holger
    74 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07535363217.36
    75 rdf:type schema:Person
    76 sg:pub.10.1007/978-3-642-22670-0_27 schema:sameAs https://app.dimensions.ai/details/publication/pub.1050124444
    77 https://doi.org/10.1007/978-3-642-22670-0_27
    78 rdf:type schema:CreativeWork
    79 sg:pub.10.1007/s00037-013-0059-7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1023864625
    80 https://doi.org/10.1007/s00037-013-0059-7
    81 rdf:type schema:CreativeWork
    82 https://doi.org/10.1016/0022-0000(83)90013-2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1038430534
    83 rdf:type schema:CreativeWork
    84 https://doi.org/10.1016/j.jcss.2009.04.001 schema:sameAs https://app.dimensions.ai/details/publication/pub.1046558319
    85 rdf:type schema:CreativeWork
    86 https://doi.org/10.1016/j.jcss.2010.06.007 schema:sameAs https://app.dimensions.ai/details/publication/pub.1018586756
    87 rdf:type schema:CreativeWork
    88 https://doi.org/10.1017/cbo9780511804090 schema:sameAs https://app.dimensions.ai/details/publication/pub.1098662846
    89 rdf:type schema:CreativeWork
    90 https://doi.org/10.1109/focs.2012.71 schema:sameAs https://app.dimensions.ai/details/publication/pub.1094542039
    91 rdf:type schema:CreativeWork
    92 https://doi.org/10.1109/sfcs.1978.37 schema:sameAs https://app.dimensions.ai/details/publication/pub.1086202543
    93 rdf:type schema:CreativeWork
    94 https://doi.org/10.1109/tit.2003.811927 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061649825
    95 rdf:type schema:CreativeWork
    96 https://doi.org/10.1137/060668092 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062849640
    97 rdf:type schema:CreativeWork
    98 https://doi.org/10.1137/1.9781611973099.10 schema:sameAs https://app.dimensions.ai/details/publication/pub.1088801430
    99 rdf:type schema:CreativeWork
    100 https://doi.org/10.1137/1.9781611973099.6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1088801524
    101 rdf:type schema:CreativeWork
    102 https://doi.org/10.1137/1.9781611973099.9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1088801559
    103 rdf:type schema:CreativeWork
    104 https://doi.org/10.1137/1.9781611973402.116 schema:sameAs https://app.dimensions.ai/details/publication/pub.1088801809
    105 rdf:type schema:CreativeWork
    106 https://doi.org/10.1137/120880240 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062869534
    107 rdf:type schema:CreativeWork
    108 https://doi.org/10.1145/2629620 schema:sameAs https://app.dimensions.ai/details/publication/pub.1037761533
    109 rdf:type schema:CreativeWork
    110 https://doi.org/10.1145/636865.636868 schema:sameAs https://app.dimensions.ai/details/publication/pub.1046390917
    111 rdf:type schema:CreativeWork
    112 https://www.grid.ac/institutes/grid.462842.e schema:alternateName Laboratoire d'Informatique Algorithmique: Fondements et Applications
    113 schema:name Cluster of Excellence (MMCI), Saarland University, Saarbrücken, Germany
    114 LIAFA, Université Paris Diderot, Paris, France
    115 Simons Institute for the Theory of Computing, Berkeley, CA, USA
    116 UC Berkeley, Berkeley, CA, USA
    117 rdf:type schema:Organization
     




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


    ...