000 02809nam a22005055i 4500
001 978-3-319-21750-5
003 DE-He213
005 20200421112043.0
007 cr nn 008mamaa
008 150724s2015 gw | s |||| 0|eng d
020 _a9783319217505
_9978-3-319-21750-5
024 7 _a10.1007/978-3-319-21750-5
_2doi
050 4 _aQA76.9.A43
072 7 _aUMB
_2bicssc
072 7 _aCOM051300
_2bisacsh
082 0 4 _a005.1
_223
100 1 _aBroniek, Przemys�aw.
_eauthor.
245 1 0 _aComputational Complexity of Solving Equation Systems
_h[electronic resource] /
_cby Przemys�aw Broniek.
250 _a1st ed. 2015.
264 1 _aCham :
_bSpringer International Publishing :
_bImprint: Springer,
_c2015.
300 _aIX, 64 p. 1 illus.
_bonline resource.
336 _atext
_btxt
_2rdacontent
337 _acomputer
_bc
_2rdamedia
338 _aonline resource
_bcr
_2rdacarrier
347 _atext file
_bPDF
_2rda
490 1 _aSpringerBriefs in Philosophy,
_x2211-4548
505 0 _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.
520 _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.
650 0 _aComputer science.
650 0 _aLogic.
650 0 _aAlgorithms.
650 0 _aMathematical logic.
650 1 4 _aComputer Science.
650 2 4 _aAlgorithm Analysis and Problem Complexity.
650 2 4 _aLogic.
650 2 4 _aMathematical Logic and Foundations.
710 2 _aSpringerLink (Online service)
773 0 _tSpringer eBooks
776 0 8 _iPrinted edition:
_z9783319217499
830 0 _aSpringerBriefs in Philosophy,
_x2211-4548
856 4 0 _uhttp://dx.doi.org/10.1007/978-3-319-21750-5
912 _aZDB-2-SCS
942 _cEBK
999 _c56741
_d56741