國立高雄大學圖資館 |

Language: English

Back

Computational complexity of solving ...

Broniek, Przemyslaw.

Computational complexity of solving equation systems

Record Type:	Electronic resources : Monograph/item
Title/Author:	Computational complexity of solving equation systemsby 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:

185313
Computational complexity.

LC Class. No.: QA267.7

Dewey Class. No.: 511.352

Computational complexity of solving equation systems
LDR:02165nmm a2200325 a 4500 001 472734
003 DE-He213
005 20160301133715.0
006 m d
007 cr nn 008maaau
008 160316s2015 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 727986
245 1 0 $a Computational complexity of solving equation systems $h [electronic resource] / $c by Przemyslaw Broniek.
260 $a Cham : $b Springer International Publishing : $b Imprint: Springer, $c 2015.
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 185313
650 0 $a Equations $x Numerical solutions. $3 185861
650 1 4 $a Computer Science. $3 212513
650 2 4 $a Algorithm Analysis and Problem Complexity. $3 273702
650 2 4 $a Logic. $3 180785
650 2 4 $a Mathematical Logic and Foundations. $3 274479
710 2 $a SpringerLink (Online service) $3 273601
773 0 $t Springer eBooks
830 0 $a SpringerBriefs in philosophy. $3 560618
856 4 0 $u http://dx.doi.org/10.1007/978-3-319-21750-5
950 $a Humanities, Social Sciences and Law (Springer-11648)