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:
Near-Optimal Asymmetric Binary Matrix Partitions Kapitel lesen Erstes Kapitel lesen

2015 | OriginalPaper | Buchkapitel

Satisfiability Algorithms and Lower Bounds for Boolean Formulas over Finite Bases

verfasst von : Ruiwen Chen

Erschienen in: Mathematical Foundations of Computer Science 2015

Verlag: Springer Berlin Heidelberg

Einloggen

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

search-config
loading …

Abstract

We give a #SAT algorithm for boolean formulas over arbitrary finite bases. Let \(B_k\) be the basis composed of all boolean functions on at most k inputs. For \(B_k\)-formulas on n inputs of size cn, our algorithm runs in time \(2^{n(1-\delta _{c,k})}\) for \(\delta _{c,k} = c^{-O(c^2k2^k)}\). We also show the average-case hardness of computing affine extractors using linear-size \(B_k\)-formulas.
We also give improved algorithms and lower bounds for formulas over finite unate bases, i.e., bases of functions which are monotone increasing or decreasing in each of the input variables.

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 Optimal Algorithms and a PTAS for Cost-Aware Scheduling
Nächstes Kapitel Randomized Polynomial Time Protocol for Combinatorial Slepian-Wolf Problem
Literatur
1.
Andreev, A.E.: On a method of obtaining more than quadratic effective lower bounds for the complexity of \(\pi \)-schemes. Vestnik Moskovskogo Universiteta. Matematika 42(1), 70–73 (1987)MathSciNetMATH
2.
Chen, R., Kabanets, V., Kolokolova, A., Shaltiel, R., Zuckerman, D.: Mining circuit lower bound proofs for meta-algorithms. In: CCC (2014)
3.
Chen, R., Kabanets, V., Saurabh, N.: An improved deterministic #SAT algorithm for small De Morgan formulas. In: Csuhaj-Varjú, E., Dietzfelbinger, M., Ésik, Z. (eds.) MFCS 2014, Part II. LNCS, vol. 8635, pp. 165–176. Springer, Heidelberg (2014)
4.
5.
6.
7.
Impagliazzo, R., Meka, R., Zuckerman, D.: Pseudorandomness from shrinkage. In: FOCS (2012)
8.
Impagliazzo, R., Nisan, N.: The effect of random restrictions on formula size. Random Struct. Algorithms 4(2), 121–134 (1993)MathSciNetCrossRefMATH
9.
Komargodski, I., Raz, R.: Average-case lower bounds for formula size. In: STOC (2013)
10.
Komargodski, I., Raz, R., Tal, A.: Improved average-case lower bounds for demorgan formula size. In: FOCS (2013)
11.
Li, X.: A new approach to affine extractors and dispersers. In: CCC (2011)
12.
13.
Santhanam, R.: Fighting perebor: New and improved algorithms for formula and qbf satisfiability. In: FOCS (2010)
14.
Seto, K., Tamaki, S.: A satisfiability algorithm and average-case hardness for formulas over the full binary basis. In: CCC (2012)
15.
Subbotovskaya, B.A.: Realizations of linear functions by formulas using and or, not. Soviet Math. Doklady 2, 110–112 (1961)MATH
16.
Williams, R.: Improving exhaustive search implies superpolynomial lower bounds. In: STOC (2010)
17.
Williams, R.: Non-uniform ACC circuit lower bounds. In: CCC (2011)
18.
Williams, R.: Algorithms for circuits and circuits for algorithms. In: CCC (2014)
19.
Metadaten
Titel
Satisfiability Algorithms and Lower Bounds for Boolean Formulas over Finite Bases
verfasst von
Ruiwen Chen
Copyright-Jahr
2015
Verlag
Springer Berlin Heidelberg
Buch
Mathematical Foundations of Computer Science 2015

Print ISBN: 978-3-662-48053-3

Electronic ISBN: 978-3-662-48054-0

Copyright-Jahr: 2015

DOI
https://doi.org/10.1007/978-3-662-48054-0_19