Computational Complexity of Solving Equation Systems

• Main Author: Broniek, Przemysław (Author)
• Corporate Author: SpringerLink (Online service)
• Format: Electronic eBook
• Language: English
• Published: Cham : Springer International Publishing : Imprint: Springer, 2015.
• Edition: 1st ed. 2015.
• Series: SpringerBriefs in Philosophy,
• Subjects: Computer science.; Logic.; Algorithms.; Mathematical logic.; Computer Science.; Algorithm Analysis and Problem Complexity.; Mathematical Logic and Foundations.

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

Table of Contents:

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