کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4950746 | 1440715 | 2016 | 11 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
A generalization of Spira's theorem and circuits with small segregators or separators
ترجمه فارسی عنوان
تعمیم قضیه اسپیرا و مدارات با جدا کننده های کوچک یا جداسازها
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
مدارهای بولی، اندازه مدار، عمق مدار، قضیه اسپیرا، پیچیدگی فضا،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
As a corollary, we show that the Boolean Circuit Value problem for circuits with constant size segregators is in deterministic SPACE(log2â¡n). Our results also imply that the Planar Circuit Value problem, which is known to be P-Complete, is in SPACE(nlogâ¡n); and that the Layered Circuit Value and Synchronous Circuit Value problems, which are both P-complete, are in SPACE(n).
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information and Computation - Volume 251, December 2016, Pages 252-262
Journal: Information and Computation - Volume 251, December 2016, Pages 252-262
نویسندگان
Anna Gál, Jing-Tang Jang,