Metraipolis › archive › dc_28dfa3e130e7

Erfüllbarkeitsproblem der Aussagenlogik — Wikipedia (de)

Source
Wikipedia (de)
Original
https://de.wikipedia.org/wiki/Erf%C3%BCllbarkeitsproblem_der_Aussagenlogik
License (as archived)
CC-BY-SA-4.0
Archived
2026-11-06T11:12:00.971Z
SHA-256 of the archived text
46d238e8618a220f9972d432f4fa18759a7c842d97420b131be922e51f084229
Stable URL of this page
https://metraipolis.com/documento/dc_28dfa3e130e7

How to cite

Erfüllbarkeitsproblem der Aussagenlogik — Wikipedia (de) — Wikipedia (de), https://de.wikipedia.org/wiki/Erf%C3%BCllbarkeitsproblem_der_Aussagenlogik (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_28dfa3e130e7 (Metraipolis archive dc_28dfa3e130e7, sha256 46d238e8618a220f9972d432f4fa18759a7c842d97420b131be922e51f084229)
BibTeX
@misc{dc28dfa3e130e7,
  title = {Erfüllbarkeitsproblem der Aussagenlogik — Wikipedia (de)},
  howpublished = {Wikipedia (de)},
  url = {https://de.wikipedia.org/wiki/Erf%C3%BCllbarkeitsproblem_der_Aussagenlogik},
  note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_28dfa3e130e7; sha256 46d238e8618a220f9972d432f4fa18759a7c842d97420b131be922e51f084229},
  year = {2026}
}

Archived text

Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (de), https://de.wikipedia.org/wiki/Erf%C3%BCllbarkeitsproblem_der_Aussagenlogik. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

Das Erfüllbarkeitsproblem der Aussagenlogik (SAT, von englisch satisfiability „Erfüllbarkeit“) ist ein Entscheidungsproblem der theoretischen Informatik. Es beschäftigt sich mit der Frage, ob eine gegebene aussagenlogische Formel F erfüllbar ist. Mit anderen Worten: Existiert eine Belegung der Variablen von F mit den Werten wahr oder falsch, sodass F zu wahr ausgewertet wird? SAT gehört zur Komplexitätsklasse NP der Probleme, die von einer nichtdeterministischen Turingmaschine in polynomieller Zeit gelöst werden können. Außerdem war SAT das erste Problem, für das NP-Vollständigkeit nachgewiesen wurde (Satz von Cook). Damit kann jedes Problem aus NP in polynomieller Zeit auf SAT zurückgeführt werden (Polynomialzeitreduktion). NP-vollständige Probleme stellen also eine Art obere Schranke für die Schwierigkeit von Problemen in NP dar. Eine deterministische Turingmaschine (etwa ein konventioneller Computer) kann SAT in exponentieller Zeit entscheiden, zum Beispiel durch das Aufstellen einer Wahrheitstabelle. Es ist kein effizienter Algorithmus für SAT bekannt und es wird allgemein vermutet, dass ein solcher Polynomialzeitalgorithmus nicht existiert. Die Frage, ob SAT in polynomieller Zeit gelöst werden kann, ist äquivalent zum P-NP-Problem, einem der bekanntesten offenen Probleme der theoretischen Informatik. Ein Großteil der Forschung beschäftigt sich mit der Entwicklung möglichst effizienter Verfahren zur Lösung von SAT in der Praxis (sogenannter SAT-Solver). Moderne SAT-Solver können Instanzen mittlerer Schwierigkeit mit hunderten Millionen Variablen oder Klauseln in praktikabler Zeit lösen. Das ist ausreichend für praktische Anwendungen, z. B. in der formalen Verifikation, in der künstlichen Intelligenz, in der Electronic Design Automation und in verschiedenen Planungs- und Schedulingalgorithmen. Sie gehören zu den Constraint Satisfaction Problems (CSP).

Tema degli esploratori: scibile generale (retro-catalogo completo della fonte, senza filtro di tema) (deposito sistematico; retro-catalogo: tutte le voci di Wikipedia in tedesco, in ordine alfabetico).
Fonte: Wikipedia in tedesco, voce «Erfüllbarkeitsproblem der Aussagenlogik» — https://de.wikipedia.org/wiki/Erf%C3%BCllbarkeitsproblem_der_Aussagenlogik
Wikidata Q875276: «problema di determinare se una formula booleana è soddisfacibile» (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q875276
Autori: i contributori di Wikipedia (cronologia: https://de.wikipedia.org/wiki/Erf%C3%BCllbarkeitsproblem_der_Aussagenlogik?action=history).
Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza.
Estratto dell'introduzione non modificato nel contenuto; revisione 265246838, consultata il 2026-11-06T11:08:28.217Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: 7e2936388751aa0fbce7b3e20c9770c183a23e18cff1b0ce3671c83b8b6d0a53