東華大學圖書館 |

Language: English

Help

回圖書館首頁

手機版館藏查詢

Back

Switch To: Labeled | MARC Mode | ISBD

Computational complexity of solving ...

Broniek, Przemyslaw.

Linked to FindBook

Google Book

Amazon

博客來

Computational complexity of solving equation systems

Record Type:	Electronic resources : 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.
[NT 15003449]:	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.
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:

523870
Computational complexity.

LC Class. No.: QA267.7

Dewey Class. No.: 511.352

Computational complexity of solving equation systems
LDR:02165nmm a2200325 a 4500 001 2009041
003 DE-He213
005 20160301133715.0
006 m d
007 cr nn 008maaau
008 160311s2015 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 2157854
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 523870
650 0 $a Equations $x Numerical solutions. $3 595328
650 1 4 $a Computer Science. $3 626642
650 2 4 $a Algorithm Analysis and Problem Complexity. $3 891007
650 2 4 $a Logic. $3 529544
650 2 4 $a Mathematical Logic and Foundations. $3 892656
710 2 $a SpringerLink (Online service) $3 836513
773 0 $t Springer eBooks
830 0 $a SpringerBriefs in philosophy. $3 1568619
856 4 0 $u http://dx.doi.org/10.1007/978-3-319-21750-5
950 $a Humanities, Social Sciences and Law (Springer-11648)