|
|
Term Satisfiability Problem for Two-Element Algebras is in QL or is NQL-Complete
|
|
|
|
|
نویسنده
|
Gorazd Tomasz A. ,Krzaczkowski Jacek
|
منبع
|
journal of universal computer science - 2013 - دوره : 19 - شماره : 10 - صفحه:1375 -1395
|
چکیده
|
We show that the term satisfiability problem for finite algebras is in nql.moreover we present a complete classification of the computational complexity of the term satisfiability problem for two-element algebras. we show that for any fixed two-element algebra the problem is either in ql or nql-complete. we show that the complexity of the considered problem, parameterized by an algebra, is determined by the clone of term operations of the algebra.
|
کلیدواژه
|
computational complexity ,solving equations ,algebra ,clones ,SAT
|
آدرس
|
Jagiellonian University, Poland, Maria Curie-Skłodowska University, Poland
|
پست الکترونیکی
|
krzacz@umcs.lublin.pl
|
|
|
|
|
|
|
|
|
|
|
|
Authors
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|