Metraipolis › archive › dc_7f8ce897fa8f

DPLL — Wikipedia

Source
Wikipedia (it)
Original
https://it.wikipedia.org/wiki/DPLL
License (as archived)
CC-BY-SA-4.0
Archived
2026-11-02T21:02:45.463Z
SHA-256 of the archived text
518a835b9fbddcb1a92f245b9dbf5aaa29f3f600fdad5555faf05b213c3cb31a
Stable URL of this page
https://metraipolis.com/documento/dc_7f8ce897fa8f

How to cite

DPLL — Wikipedia — Wikipedia (it), https://it.wikipedia.org/wiki/DPLL (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_7f8ce897fa8f (Metraipolis archive dc_7f8ce897fa8f, sha256 518a835b9fbddcb1a92f245b9dbf5aaa29f3f600fdad5555faf05b213c3cb31a)
BibTeX
@misc{dc7f8ce897fa8f,
  title = {DPLL — Wikipedia},
  howpublished = {Wikipedia (it)},
  url = {https://it.wikipedia.org/wiki/DPLL},
  note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_7f8ce897fa8f; sha256 518a835b9fbddcb1a92f245b9dbf5aaa29f3f600fdad5555faf05b213c3cb31a},
  year = {2026}
}

Archived text

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

DPLL (Davis-Putnam-Logemann-Loveland) è un algoritmo di ricerca esaustiva, basato sul backtracking, utilizzato per decidere la soddisfacibilità booleana di formule di logica proposizionale in forma normale congiuntiva (CNF), problema noto come CNF-SAT. È stato introdotto nel 1962 da Martin Davis, Hilary Putnam, George Logemann e Donald W. Loveland, e rappresenta una specializzazione del precedente algoritmo di Davis-Putnam, una procedura sviluppata nel 1960. Per questo, soprattutto nelle pubblicazioni più vecchie l'algoritmo Davis-Logemann-Loveland è spesso indicato come il "metodo Davis-Putnam" o "algoritmo DP". Altre nomenclature comuni che mantengono la distinzione fra i due sono DLL e DPLL. Il DPLL è una procedura assai efficiente, e dopo più di 40 anni forma ancora la base dei più efficienti risolutori SAT completi, così come per molti dimostratori di teoremi per frammenti di logica del primo ordine.

Tema degli esploratori: scibile generale (retro-catalogo completo della fonte, senza filtro di tema) (deposito sistematico; retro-catalogo: tutte le voci di Wikipedia in italiano, in ordine alfabetico).
Fonte: Wikipedia in italiano, voce «DPLL» — https://it.wikipedia.org/wiki/DPLL
Wikidata Q2030088 (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q2030088
Autori: i contributori di Wikipedia (cronologia: https://it.wikipedia.org/wiki/DPLL?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 151262757, consultata il 2026-11-02T20:54:57.654Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: 14cac41f7fa45249d260576e66010a819a55688fcd67065f0c33aa01d1001707