کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
420296 683920 2010 10 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Satisfiability of algebraic circuits over sets of natural numbers
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Satisfiability of algebraic circuits over sets of natural numbers
چکیده انگلیسی

We investigate the complexity of satisfiability problems   for {∪,∩,−,+,×}{∪,∩,−,+,×}-circuits computing sets of natural numbers. These problems are a natural generalization of membership problems for expressions and circuits studied by Stockmeyer and Meyer (1973) [10] and McKenzie and Wagner (2003) [8].Our work shows that satisfiability problems capture a wide range of complexity classes such as NL, P, NP, PSPACE, and beyond. We show that in several cases, satisfiability problems are harder than membership problems. In particular, we prove that testing satisfiability for {∩,+,×}{∩,+,×}-circuits is already undecidable. In contrast to this, the satisfiability for {∪,+,×}{∪,+,×}-circuits is decidable in PSPACE.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 158, Issue 13, 6 July 2010, Pages 1394–1403
نویسندگان
, , , ,