國立虎尾科技大學 |

登入

回首頁 到查詢結果 [ subject:"Computational Complexity." ]

Computational complexity of solving ...

Broniek, Przemyslaw.

Computational complexity of solving equation systems

紀錄類型:	書目-語言資料,印刷品 : Monograph/item
正題名/作者:	Computational complexity of solving equation systems/ by Przemyslaw Broniek.
作者:	Broniek, Przemyslaw.
出版者:	Cham :Springer International Publishing : : 2015.,
面頁冊數:	ix, 64 p. :ill., digital ; : 24 cm.;
Contained By:	Springer eBooks
標題:	Computational complexity. -
電子資源:	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)

筆 0 讀者評論

多媒體

評論

新增評論分享你的心得

Export

取書館別