000 02941nam a22004575i 4500
999 _c200434367
_d52579
003 DE-He213
005 20231104114355.0
007 cr nn 008mamaa
008 150724s2015 gw | s |||| 0|eng d
020 _a9783319217505
_z978-3-319-21750-5
024 7 _a10.1007/978-3-319-21750-5
_2doi
040 _aTR-AnTOB
_beng
_cTR-AnTOB
_erda
050 4 _aQA76.9.A43
072 7 _aUMB
_2bicssc
072 7 _aCOM051300
_2bisacsh
072 7 _aUMB
_2thema005.1
_223
100 1 _aBroniek, Przemysław.
_eauthor.
_4aut
_4http://id.loc.gov/vocabulary/relators/aut
245 1 0 _aComputational Complexity of Solving Equation Systems /
_cby Przemysław Broniek.
250 _a1st ed. 2015.
264 1 _aCham :
_bSpringer International Publishing :
_bImprint: Springer,
_c2015.
300 _a1 online resource
336 _atext
_btxt
_2rdacontent
337 _acomputer
_bc
_2rdamedia
338 _aonline resource
_bcr
_2rdacarrier
347 _atext file
_bPDF
_2rda
490 0 _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 software.
650 0 _aLogic.
650 0 _aLogic, Symbolic and mathematical.
650 1 4 _aAlgorithm Analysis and Problem Complexity.
_0http://scigraph.springernature.com/things/product-market-codes/I16021
650 2 4 _aLogic.
_0http://scigraph.springernature.com/things/product-market-codes/E16000
650 2 4 _aMathematical Logic and Foundations.
_0http://scigraph.springernature.com/things/product-market-codes/M24005
710 2 _aSpringerLink (Online service)
856 4 0 _3Springer eBooks
_zOnline access link to the resource
_uhttps://doi.org/10.1007/978-3-319-21750-5
942 _2lcc
_cEBK
041 _aeng