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

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