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