Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Learning with Discrete Least Squares on Multivariate Polynomial Spaces Using Evaluations at Random or Low-Discrepancy Point Sets Kapitel lesen Erstes Kapitel lesen

2015 | OriginalPaper | Buchkapitel

Characterization of the \(\#k\)–SAT Problem in Terms of Connected Components

verfasst von : Giuseppe Nicosia, Piero Conca

Erschienen in: Machine Learning, Optimization, and Big Data

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

We study the \(\#k\)–satisfiability problem, that is the problem of counting the number of different truth assignments which satisfy random Boolean expressions having k variables per clause. We design and implement an exact algorithm, which we will call Star, that solves \(\#k\)–SAT problem instances. We characterize the solution space using the connected components of a graph G,  that is a subgraph of the n dimensional hypercube representing the search space.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren
Vorheriges Kapitel Outlier Detection in Cox Proportional Hazards Models Based on the Concordance c-Index
Nächstes Kapitel A Bayesian Network Model for Fire Assessment and Prediction
Fußnoten
Literatur
1.
Ermon, S., Gomes, C.P., Selman, B.: Computing the density of states of boolean formulas. In: Cohen, D. (ed.) CP 2010. LNCS, vol. 6308, pp. 38–52. Springer, Heidelberg (2010) CrossRef
2.
Ermon, S., Gomes, C., Selman, B.: A flat histogram method for computing the density of states of combinatorial problems. In: Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, pp. 2608–2613 (2011)
3.
Montanari, A., Shah, D.: Counting good truth assignments of random k-SAT formulae. In: Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’07, pp. 1255–1264 (2007)
4.
Mitchell, D., Selman, B., Levesque, H.: Hard and easy distributions of SAT problems. In: AAAI, vol. 92, pp. 459–465 (1992)
5.
Hogg, T., Huberman, B.A., Williams, C.P.: Phase transitions and the search problem. Artif. Intell. 81(1), 1–15 (1996)MathSciNetCrossRef
6.
Monasson, R., Martin, O., Zecchina, R.: Statistical mechanics methods and phase transitions in optimizations problems. Theor. Comput. Sci. 265(1), 3–67 (2001)MATHMathSciNet
7.
Monasson, R., Zecchina, R., Kirkpatrick, S., Selman, B., Troyansky, L.: Determining computational complexity from characteristic phase transitions. Nature 400(6740), 133–137 (1999)MathSciNetCrossRef
8.
Mézard, M., Parisi, G., Zecchina, R.: Analytic and algorithmic solution of random satisfiability problems. Science 297(5582), 812–815 (2002)CrossRef
9.
Vaisman, R., Strichman, O., Gertsbakh, I.: Model counting of monotone conjunctive normal form formulas with spectr. NFORMS J. Comput. 27(2), 406–415 (2015)MathSciNetCrossRef
10.
Birnbaum, E., Lozinskii, E.L.: The good old Davis-Putnam procedure helps counting models. J. Artif. Intell. Res. 10, 457–477 (1999)MATHMathSciNet
11.
Dubois, O.: Counting the number of solutions for instances of satisfiability. Theor. Comput. Sci. 81(1), 49–64 (1991)MATHCrossRef
12.
Zhang, W.: Number of models and satisfiability of sets of clauses. Theor. Comput. Sci. 155(1), 277–288 (1996)MATHCrossRef
13.
Littman, M.L., Pitassi, T., Impagliazzo, R.: On the complexity of counting satisfying assignments. Unpublished manuscript, vol. 328, p. 329 (2001)
14.
Boufkhad, Y., Dubois, O.: Length of prime implicants and number of solutions of random CNF formulae. Theor. Comput. Sci. 215(1), 1–30 (1999)MATHMathSciNetCrossRef
15.
Garey, M.R., Johnson, D.S.: Computers and Intractability, vol. 29. W.H. Freeman, New York (2002)
16.
Papadimitriou, C.H.: Computational Complexity. John Wiley and Sons Ltd., Chichester (2003)
Metadaten
Titel
Characterization of the –SAT Problem in Terms of Connected Components
verfasst von
Giuseppe Nicosia
Piero Conca
Copyright-Jahr
2015
Buch
Machine Learning, Optimization, and Big Data

Print ISBN: 978-3-319-27925-1

Electronic ISBN: 978-3-319-27926-8

Copyright-Jahr: 2015

DOI
https://doi.org/10.1007/978-3-319-27926-8_23