دانلود کتاب Feasible Computations and Provable Complexity Properties (CBMS-NSF Regional Conference Series in Applied Mathematics) (به فارسی: محاسبات امکان پذیر و ویژگی های پیچیدگی قابل اثبات (سری کنفرانس های منطقه ای CBMS-NSF در ریاضیات کاربردی)) نوشته شده توسط «Juris Hartmanis»
اطلاعات کتاب محاسبات امکان پذیر و ویژگی های پیچیدگی قابل اثبات (سری کنفرانس های منطقه ای CBMS-NSF در ریاضیات کاربردی)
موضوع اصلی: ریاضیات
نوع: کتاب الکترونیکی
ناشر: Society for Industrial Mathematics
نویسنده: Juris Hartmanis
زبان: English
فرمت کتاب: djvu (قابل تبدیل به سایر فرمت ها)
سال انتشار: 1987
تعداد صفحه: 73
حجم کتاب: 1 مگابایت
کد کتاب: 9780898710274 , 0898710278
توضیحات کتاب محاسبات امکان پذیر و ویژگی های پیچیدگی قابل اثبات (سری کنفرانس های منطقه ای CBMS-NSF در ریاضیات کاربردی)
مروری بر تحولات جاری در تحقیق در مورد محاسبات امکان پذیر. و در نظر گرفتن این حوزه تحقیقاتی در رابطه با خواص قابل اثبات پیچیدگی محاسبات.
نویسنده با تعریف و بحث در مورد کاهش کارآمد بین مشکلات شروع می کند و خانواده ها و زبان های کامل متناظر NL، DCSL، CSL، P، NP، PTAPE، EXPTIME، و EXPTAPE را در نظر می گیرد. تعاریف و نتایج به طور یکنواخت به خانواده‌های طبیعی ساده‌تر محاسباتی زبان‌ها مانند NL، P، و CSL با استفاده از کاهش‌های n-tape bounded Log گسترش داده می‌شوند.
مسئله تعیین اینکه چه چیزی را می توان و نمی توان به طور رسمی در مورد زمان اجرای الگوریتم ها اثبات کرد، مورد بحث قرار گرفته و به مشکل ایجاد محدودیت های زمانی دقیق برای محاسبات ماشین تورینگ یک نواری مربوط می شود، و عدم توانایی در اثبات رسمی زمان اجرا برای الگوریتم ها سپس مربوط به وجود شکاف در سلسله مراتب کلاس های پیچیدگی است.
بحث پایانی در مورد این احتمال است که P=NP معروف؟ مسئله مستقل از بدیهیات سیستم های ریاضی رسمی مانند نظریه مجموعه ها است.
The author begins by defining and discussing efficient reductions between problems and considers the families and corresponding complete languages of NL, DCSL, CSL, P, NP, PTAPE, EXPTIME, and EXPTAPE. Definitions and results are uniformly extended to computationally simpler natural families of languages such as NL, P, and CSL by using Log n-tape bounded reductions.
The problem of determining what can and cannot be formally proven about running times of algorithms is discussed and related to the problem of establishing sharp time bounds for one-tape Turing machine computations, and the inability to formally prove running times for algorithms is then related to the presence of gaps in the hierarchy of complexity classes.
The concluding discussion is on the possibility that the famous P=NP? problem is independent of the axioms of formal mathematical systems such as set theory.
