SpringerBriefs in Philosophy

Computational Complexity of Solving Equation Systems

Authors: Broniek, Przemysław

Free Preview
  • Introduces the reader to problems of solving systems of equations
  • Describes and explains past solutions and provides definitions
  • Reflects the state of the art in solving equation systems
see more benefits

Buy this book

eBook $54.99
price for USA in USD
  • ISBN 978-3-319-21750-5
  • Digitally watermarked, DRM-free
  • Included format: PDF, EPUB
  • Immediate eBook download after purchase and usable on all devices
  • Bulk discounts available
Softcover $69.99
price for USA in USD
About this book

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.

Table of contents (5 chapters)

Table of contents (5 chapters)

Buy this book

eBook $54.99
price for USA in USD
  • ISBN 978-3-319-21750-5
  • Digitally watermarked, DRM-free
  • Included format: PDF, EPUB
  • Immediate eBook download after purchase and usable on all devices
  • Bulk discounts available
Softcover $69.99
price for USA in USD
Loading...

Recommended for you

Loading...

Bibliographic Information

Bibliographic Information
Book Title
Computational Complexity of Solving Equation Systems
Authors
Series Title
SpringerBriefs in Philosophy
Copyright
2015
Publisher
Springer International Publishing
Copyright Holder
The Author(s)
eBook ISBN
978-3-319-21750-5
DOI
10.1007/978-3-319-21750-5
Softcover ISBN
978-3-319-21749-9
Series ISSN
2211-4548
Edition Number
1
Number of Pages
IX, 64
Number of Illustrations
1 b/w illustrations
Topics