LEADER 03474nam  22006615  450 
001 9910299198003321
005 20220516172555.0
010   $a3-319-21750-X
024 7 $a10.1007/978-3-319-21750-5
035   $a(CKB)3710000000452174
035   $a(EBL)3567907
035   $a(SSID)ssj0001534639
035   $a(PQKBManifestationID)11875888
035   $a(PQKBTitleCode)TC0001534639
035   $a(PQKBWorkID)11496484
035   $a(PQKB)11566367
035   $a(DE-He213)978-3-319-21750-5
035   $a(MiAaPQ)EBC3567907
035   $a(PPN)187686459
035   $a(EXLCZ)993710000000452174
100   $a20150724d2015      u|         0
101 0 $aeng
135   $aur|n|---|||||
181   $ctxt
182   $cc
183   $acr
200 10$aComputational complexity of solving equation systems /$fby Przemys?aw Broniek
205   $a1st ed. 2015.
210  1$aCham :$cSpringer International Publishing :$cImprint: Springer,$d2015.
215   $a1 online resource (70 p.)
225 1 $aSpringerBriefs in Philosophy,$x2211-4548
300   $aDescription based upon print version of record.
311   $a3-319-21749-6 
320   $aIncludes bibliographical references.
327   $aAcknowledgments -- Chapter 1. Introduction -- Chapter 2. Unary algebras -- Chapter 3. Reducing CSP to SYSTERMSAT over unary algebras -- Chapter 4. Partial characterizations -- Chapter 5. Conclusions and Open Problems.
330   $aThis volume considers the computational complexity of determining whether a system of equations over a fixed algebra A has a solution. It examines in detail the two problems this leads to: SysTermSat(A) and SysPolSat(A), in which equations are built out of terms or polynomials, respectively. The book characterizes those algebras for which SysPolSat can be solved in a polynomial time. So far, studies and their outcomes have not covered algebras that generate a variety admitting type 1 in the sense of Tame Congruence Theory. Since unary algebras admit only type 1, this book focuses on these algebras to tackle the main problem. It discusses several aspects of unary algebras and proves that the Constraint Satisfaction Problem for relational structures is polynomially equivalent to SysTermSat over unary algebras. The book?s final chapters discuss partial characterizations, present conclusions, and describe the problems that are still open.
410  0$aSpringerBriefs in Philosophy,$x2211-4548
606   $aAlgorithms
606   $aLogic
606   $aLogic, Symbolic and mathematical
606   $aAlgorithm Analysis and Problem Complexity$3https://scigraph.springernature.com/ontologies/product-market-codes/I16021
606   $aLogic$3https://scigraph.springernature.com/ontologies/product-market-codes/E16000
606   $aMathematical Logic and Foundations$3https://scigraph.springernature.com/ontologies/product-market-codes/M24005
615  0$aAlgorithms.
615  0$aLogic.
615  0$aLogic, Symbolic and mathematical.
615 14$aAlgorithm Analysis and Problem Complexity.
615 24$aLogic.
615 24$aMathematical Logic and Foundations.
676   $a512.94
700   $aBroniek$b Przemys?aw$4aut$4http://id.loc.gov/vocabulary/relators/aut$01060010
801  0$bMiAaPQ
801  1$bMiAaPQ
801  2$bMiAaPQ
906   $aBOOK
912   $a9910299198003321
996   $aComputational Complexity of Solving Equation Systems$92510143
997   $aUNINA