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

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