Computational Complexity of Solving Equation Systems

این جلد پیچیدگی محاسباتی تعیین اینکه آیا سیستم معادلات روی جبر ثابت A دارای راه حل است یا خیر را در نظر می گیرد. این دو مشکل را به تفصیل بررسی می کند: SysTermSat(A) و SysPolSat(A)، که در آنها معادلات به ترتیب از جمله یا چند جمله ای ساخته می شوند. این کتاب جبرهایی را مشخص می کند که SysPolSat را می توان در یک زمان چند جمله ای حل کرد. تاکنون، مطالعات و نتایج آنها جبری‌هایی را پوشش نداده‌اند که نوع 1 را به معنای تئوری تطابق رام ایجاد می‌کنند. از آنجایی که جبرهای یکنواخت فقط نوع 1 را می پذیرند، این کتاب بر روی این جبرها تمرکز می کند تا مشکل اصلی را حل کند. چندین جنبه از جبرهای تکی را مورد بحث قرار می دهد و ثابت می کند که مشکل رضایت محدودیت برای ساختارهای رابطه ای به صورت چندجمله ای معادل SysTermSat بر روی جبرهای تکی است. فصل‌های پایانی کتاب در مورد خصوصیات جزئی بحث می‌کند، نتیجه‌گیری را ارائه می‌کند و مشکلاتی را که هنوز باز هستند توضیح می‌دهد.

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.