000728355 000__ 02714cam\a2200433Ii\4500
000728355 001__ 728355
000728355 005__ 20230306141008.0
000728355 006__ m\\\\\o\\d\\\\\\\\
000728355 007__ cr\cn\nnnunnun
000728355 008__ 150728s2015\\\\sz\a\\\\ob\\\\000\0\eng\d
000728355 020__ $$a9783319217505$$qelectronic book
000728355 020__ $$a331921750X$$qelectronic book
000728355 020__ $$z9783319217499
000728355 035__ $$aSP(OCoLC)ocn914706179
000728355 035__ $$aSP(OCoLC)914706179
000728355 040__ $$aN$T$$beng$$erda$$epn$$cN$T$$dGW5XE$$dN$T$$dIDEBK$$dYDXCP$$dAZU
000728355 049__ $$aISEA
000728355 050_4 $$aQA267.7
000728355 08204 $$a511.3/52$$223
000728355 1001_ $$aBroniek, Przemysław,$$eauthor.
000728355 24510 $$aComputational complexity of solving equation systems$$h[electronic resource] /$$cPrzemysław Broniek.
000728355 264_1 $$aCham :$$bSpringer,$$c2015.
000728355 300__ $$a1 online resource (ix, 64 pages) :$$billustration.
000728355 336__ $$atext$$btxt$$2rdacontent
000728355 337__ $$acomputer$$bc$$2rdamedia
000728355 338__ $$aonline resource$$bcr$$2rdacarrier
000728355 4901_ $$aSpringerBriefs in philosophy,$$x2211-4548
000728355 504__ $$aIncludes bibliographical references.
000728355 5050_ $$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.
000728355 506__ $$aAccess limited to authorized users.
000728355 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.
000728355 588__ $$aOnline resource; title from PDF title page (SpringerLink, viewed July 29, 2015).
000728355 650_0 $$aComputational complexity.
000728355 650_0 $$aEquations$$xNumerical solutions.
000728355 830_0 $$aSpringerBriefs in philosophy.
000728355 852__ $$bebk
000728355 85640 $$3SpringerLink$$uhttps://univsouthin.idm.oclc.org/login?url=http://link.springer.com/10.1007/978-3-319-21750-5$$zOnline Access$$91397441.1
000728355 909CO $$ooai:library.usi.edu:728355$$pGLOBAL_SET
000728355 980__ $$aEBOOK
000728355 980__ $$aBIB
000728355 982__ $$aEbook
000728355 983__ $$aOnline
000728355 994__ $$a92$$bISE