کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
437782 | 690185 | 2011 | 13 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Non-mitotic sets
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
We study the question of the existence of non-mitotic sets in NP. We show under various hypotheses that
• 1-tt-mitoticity and m-mitoticity differ on NP.
• T-autoreducibility and T-mitoticity differ on NP (this contrasts the situation in the recursion theoretic setting, where Ladner showed that autoreducibility and mitoticity coincide).
• 2-tt-autoreducibility does not imply weak 2-tt-mitoticity (from this it follows that autoreducibility and mitoticity are not equivalent for all reducibilities between 2-tt and T, although the notions coincide for m- and 1-tt-reducibility).
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 410, Issues 21–23, 17 May 2009, Pages 2011-2023
Journal: Theoretical Computer Science - Volume 410, Issues 21–23, 17 May 2009, Pages 2011-2023