Metraipolis › archive › dc_e49236bf6e76
3-SAT — Wikipedia (de)
- Source
- Wikipedia (de)
- Original
- https://de.wikipedia.org/wiki/3-SAT
- License (as archived)
- CC-BY-SA-4.0
- Archived
- 2026-10-07T21:09:21.713Z
- SHA-256 of the archived text
fefdb929ff75cf8e7c3f4c06d2780381dbb1b9e22e9b785de506e25f347c8a17- Stable URL of this page
https://metraipolis.com/documento/dc_e49236bf6e76
How to cite
3-SAT — Wikipedia (de) — Wikipedia (de), https://de.wikipedia.org/wiki/3-SAT (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_e49236bf6e76 (Metraipolis archive dc_e49236bf6e76, sha256 fefdb929ff75cf8e7c3f4c06d2780381dbb1b9e22e9b785de506e25f347c8a17)
BibTeX
@misc{dce49236bf6e76,
title = {3-SAT — Wikipedia (de)},
howpublished = {Wikipedia (de)},
url = {https://de.wikipedia.org/wiki/3-SAT},
note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_e49236bf6e76; sha256 fefdb929ff75cf8e7c3f4c06d2780381dbb1b9e22e9b785de506e25f347c8a17},
year = {2026}
}Archived text
Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (de), https://de.wikipedia.org/wiki/3-SAT. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
3-SAT ist eine Variante des Erfüllbarkeitsproblems der Aussagenlogik (von englisch satisfiability ‚Erfüllbarkeit‘, kurz SAT). Es beschäftigt sich mit der Frage, ob eine in konjunktiver Normalform vorliegende aussagenlogische Formel F {\displaystyle F} , die höchstens 3 Literale pro Klausel enthält, erfüllbar ist. Ein Beispiel für eine solche Formel: F = ( x 1 ¯ ∨ x 2 ∨ x 3 ) ∧ ( x 2 ∨ x 3 ¯ ∨ x 4 ) ∧ ( x 1 ∨ x 2 ¯ ) {\displaystyle F=({\overline {x_{1}}}\vee x_{2}\vee x_{3})\wedge (x_{2}\vee {\overline {x_{3}}}\vee x_{4})\wedge (x_{1}\vee {\overline {x_{2}}})} Gesucht ist nun eine Belegung der Variablen x 1 {\displaystyle x_{1}} bis x 4 {\displaystyle x_{4}} mit 0 oder 1, für die F den Wert 1 (wahr) annimmt. Falls es eine solche Belegung gibt, ist F erfüllbar, sonst nicht. Wie bei allen NP-vollständigen Problemen ist es „einfach“, einen Lösungskandidaten auf seine Gültigkeit zu überprüfen, hier also festzustellen, ob eine vorgegebene Belegung der Variablen die Formel erfüllt. Das Auffinden eines gültigen Lösungskandidaten ist jedoch im Allgemeinen „schwierig“, da heute keine Methode bekannt ist, eine erfüllende Belegung in polynomieller Zeit zu finden. Allgemeiner definiert man das k-SAT-Problem als die Frage, ob eine beliebige aussagenlogische Formel, die in konjunktiver Normalform mit k Literalen pro Klausel vorliegt, erfüllbar ist. Das k-SAT-Problem für k > 3 {\displaystyle k>3} lässt sich auf 3-SAT zurückführen, damit gilt: Alle k-SAT-Probleme für k ≥ 3 {\displaystyle k\geq 3} sind NP-vollständig. 2-SAT liegt in der Komplexitätsklasse NL, 1-SAT liegt in der Komplexitätsklasse L. Das allgemeine Erfüllbarkeitsproblem der Aussagenlogik (SAT) lässt sich auf 3-SAT polynomiell reduzieren, und somit ist 3-SAT nach dem Satz von Cook NP-vollständig. 3-SAT lässt sich wiederum u. a. auf das Cliquenproblem, das Rucksackproblem und auf den gerichteten Hamiltonkreis (DHC) polynomiell reduzieren, wodurch auch diese Probleme als NP-schwer nachgewiesen sind.
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 «3-SAT» — https://de.wikipedia.org/wiki/3-SAT
Wikidata Q339688 (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q339688
Autori: i contributori di Wikipedia (cronologia: https://de.wikipedia.org/wiki/3-SAT?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 267662259, consultata il 2026-10-07T20:40:57.599Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: 1a01608408da38cfa16916c72bf806dca5da8d2c387d4d90a01b58c00fa63626