國立虎尾科技大學 |

Computational complexity of solving equation systems

Record Type:	Language materials, printed : Monograph/item
Title/Author:	Computational complexity of solving equation systems/ by Przemyslaw Broniek.
Author:	Broniek, Przemyslaw.
Published:	Cham :Springer International Publishing : : 2015.,
Description:	ix, 64 p. :ill., digital ; : 24 cm.;
Contained By:	Springer eBooks
Subject:	Computational complexity. -
Online resource:	http://dx.doi.org/10.1007/978-3-319-21750-5
ISBN:	9783319217505 (electronic bk.)

Computational complexity of solving equation systems
Broniek, Przemyslaw.

Computational complexity of solving equation systems[electronic resource] /by Przemyslaw Broniek. - Cham :Springer International Publishing :2015. - ix, 64 p. :ill., digital ;24 cm. - SpringerBriefs in philosophy,2211-4548. - SpringerBriefs in philosophy..

Acknowledgments -- 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.

This 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.

ISBN: 9783319217505 (electronic bk.)

Standard No.: 10.1007/978-3-319-21750-5doiSubjects--Topical Terms:

527777
Computational complexity.

LC Class. No.: QA267.7

Dewey Class. No.: 511.352

Computational complexity of solving equation systems
LDR:02165nam a2200325 a 4500 001 836869
003 DE-He213
005 20160301133715.0
006 m d
007 cr nn 008maaau
008 160421s2015 gw s 0 eng d
020 $a 9783319217505 (electronic bk.)
020 $a 9783319217499 (paper)
024 7 $a 10.1007/978-3-319-21750-5 $2 doi
035 $a 978-3-319-21750-5
040 $a GP $c GP
041 0 $a eng
050 4 $a QA267.7
072 7 $a UMB $2 bicssc
072 7 $a COM051300 $2 bisacsh
082 0 4 $a 511.352 $2 23
090 $a QA267.7 $b .B869 2015
100 1 $a Broniek, Przemyslaw. $3 1067278
245 1 0 $a Computational complexity of solving equation systems $h [electronic resource] / $c by Przemyslaw Broniek.
260 $a Cham : $c 2015. $b Springer International Publishing : $b Imprint: Springer,
300 $a ix, 64 p. : $b ill., digital ; $c 24 cm.
490 1 $a SpringerBriefs in philosophy, $x 2211-4548
505 0 $a Acknowledgments -- 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 $a This 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 $a Computational complexity. $3 527777
650 0 $a Equations $x Numerical solutions. $3 528051
650 1 4 $a Computer Science. $3 593922
650 2 4 $a Algorithm Analysis and Problem Complexity. $3 593923
650 2 4 $a Logic. $3 558909
650 2 4 $a Mathematical Logic and Foundations. $3 669393
710 2 $a SpringerLink (Online service) $3 593884
773 0 $t Springer eBooks
830 0 $a SpringerBriefs in philosophy. $3 890808
856 4 0 $u http://dx.doi.org/10.1007/978-3-319-21750-5
950 $a Humanities, Social Sciences and Law (Springer-11648)