The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2006

AUTHORS

Parikshit Gopalan , Phokion G. Kolaitis , Elitza N. Maneva , Christos H. Papadimitriou

ABSTRACT

Given a Boolean formula, do its solutions form a connected subgraph of the hypercube? This and other related connectivity considerations underlie recent work on random Boolean satisfiability. We study connectivity properties of the space of solutions of Boolean formulas, and establish computational and structural dichotomies. Specifically, we first establish a dichotomy theorem for the complexity of the st-connectivity problem for Boolean formulas in Schaefer’s framework. Our result asserts that the tractable side is more generous than the tractable side in Schaefer’s dichotomy theorem for satisfiability, while the intractable side is PSPACE-complete. For the connectivity problem, we establish a dichotomy along the same boundary between membership in coNP and PSPACE-completeness. Furthermore, we establish a structural dichotomy theorem for the diameter of the connected components of the solution space: for the PSPACE-complete cases, the diameter can be exponential, but in all other cases it is linear. Thus, small diameter and tractability of the st-connectivity problem are remarkably aligned. More... »

PAGES

346-357

Book

TITLE

Automata, Languages and Programming

ISBN

978-3-540-35904-3
978-3-540-35905-0

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/11786986_31

DOI

http://dx.doi.org/10.1007/11786986_31

DIMENSIONS

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


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/0801", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Artificial Intelligence and Image Processing", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Georgia Tech", 
          "id": "http://www.grid.ac/institutes/grid.213917.f", 
          "name": [
            "Georgia Tech"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Gopalan", 
        "givenName": "Parikshit", 
        "id": "sg:person.011621327233.73", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011621327233.73"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "IBM Almaden Research Center", 
          "id": "http://www.grid.ac/institutes/grid.481551.c", 
          "name": [
            "IBM Almaden Research Center"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Kolaitis", 
        "givenName": "Phokion G.", 
        "id": "sg:person.0752641744.70", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0752641744.70"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "UC Berkeley", 
          "id": "http://www.grid.ac/institutes/grid.47840.3f", 
          "name": [
            "UC Berkeley"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Maneva", 
        "givenName": "Elitza N.", 
        "id": "sg:person.011267061237.09", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011267061237.09"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "UC Berkeley", 
          "id": "http://www.grid.ac/institutes/grid.47840.3f", 
          "name": [
            "UC Berkeley"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Papadimitriou", 
        "givenName": "Christos H.", 
        "id": "sg:person.013233165465.63", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013233165465.63"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2006", 
    "datePublishedReg": "2006-01-01", 
    "description": "Given a Boolean formula, do its solutions form a connected subgraph of the hypercube? This and other related connectivity considerations underlie recent work on random Boolean satisfiability. We study connectivity properties of the space of solutions of Boolean formulas, and establish computational and structural dichotomies. Specifically, we first establish a dichotomy theorem for the complexity of the st-connectivity problem for Boolean formulas in Schaefer\u2019s framework. Our result asserts that the tractable side is more generous than the tractable side in Schaefer\u2019s dichotomy theorem for satisfiability, while the intractable side is PSPACE-complete. For the connectivity problem, we establish a dichotomy along the same boundary between membership in coNP and PSPACE-completeness. Furthermore, we establish a structural dichotomy theorem for the diameter of the connected components of the solution space: for the PSPACE-complete cases, the diameter can be exponential, but in all other cases it is linear. Thus, small diameter and tractability of the st-connectivity problem are remarkably aligned.", 
    "editor": [
      {
        "familyName": "Bugliesi", 
        "givenName": "Michele", 
        "type": "Person"
      }, 
      {
        "familyName": "Preneel", 
        "givenName": "Bart", 
        "type": "Person"
      }, 
      {
        "familyName": "Sassone", 
        "givenName": "Vladimiro", 
        "type": "Person"
      }, 
      {
        "familyName": "Wegener", 
        "givenName": "Ingo", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/11786986_31", 
    "inLanguage": "en", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-540-35904-3", 
        "978-3-540-35905-0"
      ], 
      "name": "Automata, Languages and Programming", 
      "type": "Book"
    }, 
    "keywords": [
      "st-connectivity problem", 
      "Boolean formulas", 
      "Boolean satisfiability", 
      "dichotomy theorem", 
      "connected subgraph", 
      "Schaefer\u2019s framework", 
      "connectivity problem", 
      "PSPACE-completeness", 
      "connected components", 
      "solution space", 
      "connectivity considerations", 
      "satisfiability", 
      "connectivity properties", 
      "space of solutions", 
      "Schaefer\u2019s dichotomy theorem", 
      "framework", 
      "computational", 
      "subgraphs", 
      "hypercube", 
      "complexity", 
      "solution", 
      "recent work", 
      "space", 
      "coNP", 
      "tractability", 
      "connectivity", 
      "work", 
      "theorem", 
      "formula", 
      "consideration", 
      "results", 
      "membership", 
      "components", 
      "side", 
      "boundaries", 
      "cases", 
      "dichotomy", 
      "same boundary", 
      "diameter", 
      "small diameter", 
      "properties", 
      "problem", 
      "structural dichotomy", 
      "related connectivity considerations", 
      "random Boolean satisfiability", 
      "tractable side", 
      "intractable side", 
      "structural dichotomy theorem", 
      "PSPACE-complete cases"
    ], 
    "name": "The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies", 
    "pagination": "346-357", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1046014572"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/11786986_31"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/11786986_31", 
      "https://app.dimensions.ai/details/publication/pub.1046014572"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2021-12-01T20:10", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20211201/entities/gbq_results/chapter/chapter_431.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/11786986_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/11786986_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/11786986_31'

Turtle is a human-readable linked data format.

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

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

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


 

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

151 TRIPLES      23 PREDICATES      75 URIs      68 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/11786986_31 schema:about anzsrc-for:08
2 anzsrc-for:0801
3 schema:author N149a5b67e7794bf4a898d5a440195beb
4 schema:datePublished 2006
5 schema:datePublishedReg 2006-01-01
6 schema:description Given a Boolean formula, do its solutions form a connected subgraph of the hypercube? This and other related connectivity considerations underlie recent work on random Boolean satisfiability. We study connectivity properties of the space of solutions of Boolean formulas, and establish computational and structural dichotomies. Specifically, we first establish a dichotomy theorem for the complexity of the st-connectivity problem for Boolean formulas in Schaefer’s framework. Our result asserts that the tractable side is more generous than the tractable side in Schaefer’s dichotomy theorem for satisfiability, while the intractable side is PSPACE-complete. For the connectivity problem, we establish a dichotomy along the same boundary between membership in coNP and PSPACE-completeness. Furthermore, we establish a structural dichotomy theorem for the diameter of the connected components of the solution space: for the PSPACE-complete cases, the diameter can be exponential, but in all other cases it is linear. Thus, small diameter and tractability of the st-connectivity problem are remarkably aligned.
7 schema:editor Nd734bea9fc1e49bca827e30b3c298ae3
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf Nd92d00e4d37546118cac59d72a27da94
12 schema:keywords Boolean formulas
13 Boolean satisfiability
14 PSPACE-complete cases
15 PSPACE-completeness
16 Schaefer’s dichotomy theorem
17 Schaefer’s framework
18 boundaries
19 cases
20 coNP
21 complexity
22 components
23 computational
24 connected components
25 connected subgraph
26 connectivity
27 connectivity considerations
28 connectivity problem
29 connectivity properties
30 consideration
31 diameter
32 dichotomy
33 dichotomy theorem
34 formula
35 framework
36 hypercube
37 intractable side
38 membership
39 problem
40 properties
41 random Boolean satisfiability
42 recent work
43 related connectivity considerations
44 results
45 same boundary
46 satisfiability
47 side
48 small diameter
49 solution
50 solution space
51 space
52 space of solutions
53 st-connectivity problem
54 structural dichotomy
55 structural dichotomy theorem
56 subgraphs
57 theorem
58 tractability
59 tractable side
60 work
61 schema:name The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies
62 schema:pagination 346-357
63 schema:productId N54ff7c476604441e8d596431bdd57ead
64 N91b427f71009442495f32f8c6496501e
65 schema:publisher N794d492626594ae19da90726af8bab58
66 schema:sameAs https://app.dimensions.ai/details/publication/pub.1046014572
67 https://doi.org/10.1007/11786986_31
68 schema:sdDatePublished 2021-12-01T20:10
69 schema:sdLicense https://scigraph.springernature.com/explorer/license/
70 schema:sdPublisher Nbf9dc833831b4c978d2cf4034e18cc1c
71 schema:url https://doi.org/10.1007/11786986_31
72 sgo:license sg:explorer/license/
73 sgo:sdDataset chapters
74 rdf:type schema:Chapter
75 N1102dcf49ac24db4abee088ef680def2 rdf:first sg:person.0752641744.70
76 rdf:rest Nc544e3052ace4ba7881ed08c7a89c218
77 N149a5b67e7794bf4a898d5a440195beb rdf:first sg:person.011621327233.73
78 rdf:rest N1102dcf49ac24db4abee088ef680def2
79 N319a6a6df9e7494999450173ddae6887 schema:familyName Preneel
80 schema:givenName Bart
81 rdf:type schema:Person
82 N4f924d8e5af44efd8ca5d0f5d4c4dbe2 rdf:first sg:person.013233165465.63
83 rdf:rest rdf:nil
84 N5051000454984a0598daaa9747c3f8b7 schema:familyName Sassone
85 schema:givenName Vladimiro
86 rdf:type schema:Person
87 N54ff7c476604441e8d596431bdd57ead schema:name doi
88 schema:value 10.1007/11786986_31
89 rdf:type schema:PropertyValue
90 N794d492626594ae19da90726af8bab58 schema:name Springer Nature
91 rdf:type schema:Organisation
92 N8c5660ecb14247b090d328f14e6a356a schema:familyName Wegener
93 schema:givenName Ingo
94 rdf:type schema:Person
95 N91b427f71009442495f32f8c6496501e schema:name dimensions_id
96 schema:value pub.1046014572
97 rdf:type schema:PropertyValue
98 N98473eb59752458287198fedef334201 rdf:first N319a6a6df9e7494999450173ddae6887
99 rdf:rest Ncb9f04d8681848e696c1ca25f95e9bee
100 Nbc08815e99b54756891ead8044746a4e schema:familyName Bugliesi
101 schema:givenName Michele
102 rdf:type schema:Person
103 Nbf9dc833831b4c978d2cf4034e18cc1c schema:name Springer Nature - SN SciGraph project
104 rdf:type schema:Organization
105 Nc544e3052ace4ba7881ed08c7a89c218 rdf:first sg:person.011267061237.09
106 rdf:rest N4f924d8e5af44efd8ca5d0f5d4c4dbe2
107 Ncb9f04d8681848e696c1ca25f95e9bee rdf:first N5051000454984a0598daaa9747c3f8b7
108 rdf:rest Nec5e5f05a7bf4f348a30cfbef2432626
109 Nd734bea9fc1e49bca827e30b3c298ae3 rdf:first Nbc08815e99b54756891ead8044746a4e
110 rdf:rest N98473eb59752458287198fedef334201
111 Nd92d00e4d37546118cac59d72a27da94 schema:isbn 978-3-540-35904-3
112 978-3-540-35905-0
113 schema:name Automata, Languages and Programming
114 rdf:type schema:Book
115 Nec5e5f05a7bf4f348a30cfbef2432626 rdf:first N8c5660ecb14247b090d328f14e6a356a
116 rdf:rest rdf:nil
117 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
118 schema:name Information and Computing Sciences
119 rdf:type schema:DefinedTerm
120 anzsrc-for:0801 schema:inDefinedTermSet anzsrc-for:
121 schema:name Artificial Intelligence and Image Processing
122 rdf:type schema:DefinedTerm
123 sg:person.011267061237.09 schema:affiliation grid-institutes:grid.47840.3f
124 schema:familyName Maneva
125 schema:givenName Elitza N.
126 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011267061237.09
127 rdf:type schema:Person
128 sg:person.011621327233.73 schema:affiliation grid-institutes:grid.213917.f
129 schema:familyName Gopalan
130 schema:givenName Parikshit
131 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011621327233.73
132 rdf:type schema:Person
133 sg:person.013233165465.63 schema:affiliation grid-institutes:grid.47840.3f
134 schema:familyName Papadimitriou
135 schema:givenName Christos H.
136 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013233165465.63
137 rdf:type schema:Person
138 sg:person.0752641744.70 schema:affiliation grid-institutes:grid.481551.c
139 schema:familyName Kolaitis
140 schema:givenName Phokion G.
141 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0752641744.70
142 rdf:type schema:Person
143 grid-institutes:grid.213917.f schema:alternateName Georgia Tech
144 schema:name Georgia Tech
145 rdf:type schema:Organization
146 grid-institutes:grid.47840.3f schema:alternateName UC Berkeley
147 schema:name UC Berkeley
148 rdf:type schema:Organization
149 grid-institutes:grid.481551.c schema:alternateName IBM Almaden Research Center
150 schema:name IBM Almaden Research Center
151 rdf:type schema:Organization
 




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


...