Classes of Boolean Formulae with Effectively Solvable SAT

Kód výsledku v IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F10%3A10051502" target="_blank" >RIV/00216208:11320/10:10051502 - isvavai.cz</a>
Výsledek na webu
—
DOI - Digital Object Identifier
—

Jazyk výsledku
angličtina
Název v původním jazyce
Classes of Boolean Formulae with Effectively Solvable SAT
Popis výsledku v původním jazyce
We present an overview of known classes of Boolean formulae for which polynomial time algorithms for satisfiability testing (SAT) are known. We will summarize basic properties of these classes and their mutual relations with respect to inclusion. One ofthese classes on which we focus our attention in particular is the class of Single Lookahead Unit Resolution formulae (SLUR). We will define a hierarchy of classes which constitutes a generalization of the SLUR class, and prove its properties.
Název v anglickém jazyce
Classes of Boolean Formulae with Effectively Solvable SAT
Popis výsledku anglicky
We present an overview of known classes of Boolean formulae for which polynomial time algorithms for satisfiability testing (SAT) are known. We will summarize basic properties of these classes and their mutual relations with respect to inclusion. One ofthese classes on which we focus our attention in particular is the class of Single Lookahead Unit Resolution formulae (SLUR). We will define a hierarchy of classes which constitutes a generalization of the SLUR class, and prove its properties.

Rok uplatnění
2010
Kód důvěrnosti údajů
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Podobné výsledky(10)