>
Fa   |   Ar   |   En
   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
  
 
 

Copyright 2023
Islamic World Science Citation Center
All Rights Reserved