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)

pdf AMI_35_from75to94.pdf Download (268kB)

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
Szerző:	Szerző neve MTMT azonosító ORCID azonosító Közreműködés Kusper, Gábor NEM RÉSZLETEZETT NEM RÉSZLETEZETT Szerző Csőke, Lajos NEM RÉSZLETEZETT NEM RÉSZLETEZETT Szerző Kovásznai, Gergely NEM RÉSZLETEZETT NEM RÉSZLETEZETT Szerző
Kapcsolódó URL-ek:	Folyóirat honlapja
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