کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4608910 | 1631475 | 2007 | 9 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
A note on parallel and alternating time
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
آنالیز ریاضی
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
A long standing open question in complexity theory over the reals is the relationship between parallel time and quantifier alternation. It is known that alternating digital quantifiers is weaker than parallel time, which in turn is weaker than alternating unrestricted (real) quantifiers. In this note we consider some complexity classes defined through alternation of mixed digital and unrestricted quantifiers in different patterns. We show that the class of sets decided in parallel polynomial time is sandwiched between two such classes for different patterns.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Complexity - Volume 23, Issues 4–6, August–December 2007, Pages 594-602
Journal: Journal of Complexity - Volume 23, Issues 4–6, August–December 2007, Pages 594-602