New Complexity Results for Lukasiewicz Logic

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985807%3A_____%2F19%3A00491990" target="_blank" >RIV/67985807:_____/19:00491990 - isvavai.cz</a>
Result on the web
<a href="http://hdl.handle.net/11104/0285586" target="_blank" >http://hdl.handle.net/11104/0285586</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1007/s00500-018-3365-9" target="_blank" >10.1007/s00500-018-3365-9</a>

Result language
angličtina
Original language name
New Complexity Results for Lukasiewicz Logic
Original language description
One aspect that has been poorly studied in multiple-valued logics, and in particular in Lukasiewicz logic, is the generation of instances of varying difficulty for evaluating, comparing and improving satisfiability solvers. With the ultimate goal of finding challenging benchmarks for Lukasiewicz satisfiability solvers, we start by defining a natural and intuitive class of clausal forms (simple L-clausal forms) and studying their complexity. Since we prove that the satisfiability problem of simple L-clausal forms can be solved in linear time, we then define two new classes of clausal forms (L-clausal forms and restricted L-clausal forms) that truly exploit the non-lattice operations of Lukasiewicz logic and whose satisfiability problems are NP-complete when clauses have at least three literals, and admit linear-time algorithms when clauses have at most two literals. We also define an efficient satisfiability preserving translation of Lukasiewicz logic formulas into L-clausal forms. Finally, we describe a random generator of L-clausal forms and report on an empirical investigation in which we identify an easy-hard-easy pattern and a phase transition phenomenon for L-clausal forms.
Czech name
—
Czech description
—

Type
J<sub>imp</sub> - Article in a specialist periodical, which is included in the Web of Science database
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Project
<a href="/en/project/GA17-04630S" target="_blank" >GA17-04630S: Predicate graded logics and their applications to computer science</a><br>
Continuities
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Publication year
2019
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Similar results(10)