کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
421989 | 684999 | 2008 | 13 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
On Relativizations of the P =? NP Question for Several Structures
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
We consider the uniform model of computation over arbitrary structures with two constants. For several structures, including structures over the reals, we construct oracles which imply that the relativized versions of P and NP are equal or are not equal. Moreover we discuss some special features of these oracles resulting from the undecidability of halting problems in order to explain the difficulties to define structures of finite signature which satisfy P = NP. We show that there are oracles which lose their non-deterministic self-reducibility which is sufficient for a recursive definition if their elements are compressed to tuples of fixed length.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Electronic Notes in Theoretical Computer Science - Volume 221, 25 December 2008, Pages 71-83
Journal: Electronic Notes in Theoretical Computer Science - Volume 221, 25 December 2008, Pages 71-83