Computational Complexity of SAT, XSAT and NAE-SAT

For linear and mixed Horn CNF formulas

Autori

• Tatjana Schmidt

Parametri

Pagine

172pagine

Tempo di lettura

7ore

• Natura
• Natura, animali

Maggiori informazioni sul libro

Focusing on the Mixed Horn formula class (MHF), this thesis explores the SAT problem, which determines the satisfiability of CNF formulas. Highlighting MHF's significance, it connects this subclass to various NP-complete problems, such as Feedback Vertex Set and Vertex Cover. The work demonstrates that SAT remains NP-complete for certain MHF subclasses and introduces algorithms that improve upon existing time bounds. Additionally, it examines the computational complexity of variants like not-all-equal SAT and exact SAT within linear CNF formulas.

Per saperne di più

Lingua: Inglese

Pubblicato: 2015

(In brossura)