Simplifying the propositional satisfiability problem by sub-model propagation

Kusper, Gábor, Csőke, Lajos, Kovásznai, Gergely (2008) Simplifying the propositional satisfiability problem by sub-model propagation Annales Mathematicae et Informaticae. 35. pp. 75-94. ISSN 1787-5021 (Print), 1787-6117 (Online)

[thumbnail of AMI_35_from75to94.pdf] pdf
AMI_35_from75to94.pdf

Download (268kB) [error in script]

Absztrakt (kivonat)

We describes cases when we can simplify a general SAT problem instance by sub-model propagation. Assume that we test our input clause set whether it is blocked or not, because we know that a blocked clause set can be solved in polynomial time. If the input clause set is not blocked, but some clauses are blocked, then what can we do? Can we use the blocked clauses to simplify the clause set? The Blocked Clear Clause Rule and the Independent Blocked Clause Rule describe cases when the answer is yes. The other two independent clause rules, the Independent Nondecisive- and Independent Strongly Nondecisive Clause Rules describe cases when we can use nondecisive and strongly nondecisive clauses to simplify a general SAT problem instance.

Mű típusa: Folyóiratcikk - Journal article
Szerző:
Szerző neve
Email
MTMT azonosító
ORCID azonosító
Közreműködés
Kusper, Gábor
NEM RÉSZLETEZETT
NEM RÉSZLETEZETT
NEM RÉSZLETEZETT
Szerző
Csőke, Lajos
NEM RÉSZLETEZETT
NEM RÉSZLETEZETT
NEM RÉSZLETEZETT
Szerző
Kovásznai, Gergely
NEM RÉSZLETEZETT
NEM RÉSZLETEZETT
NEM RÉSZLETEZETT
Szerző
Kapcsolódó URL-ek:
Kulcsszavak: SAT, blocked clause, nondecisive clause
Nyelv: angol
Kötetszám: 35.
ISSN: 1787-5021 (Print), 1787-6117 (Online)
Felhasználó: Tibor Gál
Dátum: 05 Már 2019 16:17
Utolsó módosítás: 05 Már 2019 16:17
URI: http://publikacio.uni-eszterhazy.hu/id/eprint/3103
Műveletek (bejelentkezés szükséges)
Tétel nézet Tétel nézet