بخشی از پاورپوینت
اسلاید 1 :
مقدمه
تئوری پيچيدگی
ايجاد زيربنای رياضياتی لازم برای محاسبات کارآ
تئوری اثبات
معرفی سيستم‌های اثبات گوناگون
فرماليزه نمودن يک منطق
بررسی توانايی‌ها و محدوديت‌ها
قابليت بيان يک قضيه
قابليت اثبات يک قضيه
اسلاید 2 :
مقدمه (ادامه)
پيچيدگی اثبات
حاصل مواجهه تئوری پيچيدگی و تئوری اثبات
بررسی سيستم‌های اثبات گوناگون
تعيين حد بالا و پايين برای کوچک‌ترين اثبات‌ها
تعريف منطق‌هايی برای مشخص‌ساختن کلاس‌های پيچيدگی
نمونه‌هايی از منطق‌های کلاسيک مانند و PV
نمونه‌ای از منطق‌های شهودگرا مانند IPV
اسلاید 3 :
منطق ساختی
مهم‌ترين منطق شهودگرای موجود
اثبات معادل است با برنامه
تئوری انواع
از مهم‌ترين فرماليسم‌های موجود برای منطق ساختی
فقط قابليت بيان توابع کامل
نسخه‌هايی با قابليت بيان توابع جزيی موجودند
همه کلاس‌های پيچيدگی معروف در مجموعه توابع کامل هستند
اسلاید 4 :
تئوری انواع
قابليت بيان توصيف يک برنامه يا مساله
قابليت بيان اثبات يک توصيف
از طريق قوانين معرفی و حذف عملگرها و استقرا
وجود نرم‌افزارهای گوناگون برای کار با تئوری انواع
مانند uprl
قابليت تعبير توسط تئوری مارتين-لوف
اسلاید 5 :
هدف پايان‌نامه
تعريف برخی کلاس‌های پيچيدگی در تئوری انواع
ارائه اصول و قوانين استنتاج به نحوی که
اثبات يک قضيه با اين اصول و قوانين معادل است با بودن در کلاس پيچيدگی مربوطه
برخورداری از خصوصيات مهم تئوری انواع
قابليت خوانده‌شدن به صورت انواع
خصوصيت نوع به جای گزاره
خصوصيت نوع به جای برنامه
خصوصيت نوع به جای مجموعه
اسلاید 6 :
مزايا
عدم نياز به اثبات بودن در يک کلاس پيچيدگی
وجود اثبات برای يک مساله نشانگر داشتن راه‌حلی در کلاس پيچيدگی مربوطه است
اثبات عدم‌اثبات‌پذيری در اين تئوری نشانگر عدم وجود در يک کلاس پيچيدگی است
استفاده از اثبات‌گرهای خودکار
اسلاید 7 :
کارهای پيشين
مشخص‌کردن کلاس‌های پيچيدگی در
مدل‌های محدود
توصيف مساله‌ها
اثبات مساله‌ها
پياده‌سازی مساله‌ها
اسلاید 8 :
مدل‌های محدود
مدل‌های محدود
کاربرد بسيار در مسائل مهندسی و رياضی
مدل نمودن بسياری از پديده‌ها در قالب گراف‌ها و ديگر مدل‌های محدود
مدل‌های محدود و کلاس‌های پيچيدگی
سختی توصيف يک مدل
سختی توصيف يک خصوصيت در يک مدل
سختی بررسی يک خصوصيت برای يک مدل
اسلاید 9 :
توصيف مساله‌ها
توصيف مدلی است معمولا منطقی شامل
توصيف ورودی‌های مساله و پيش‌شرط‌ها
توصيف خروجی‌های مساله
رابطه ورودی‌ها و خروجی‌ها
زبان‌های توصيف مانند: منطق‌های مرتبه اول و دوم، تئوری انواع، زبان B
اسلاید 10 :
توصيف مساله‌ها (ادامه)
مبحث پيچيدگی در توصيف
محدودشده زبان توصيفی
قابليت بيان توصيف يک برنامه معادل است با وجود راه‌حلی در کلاس پيچيدگی مورد توصيف
برخی از کارهای مهم در اين زمينه عبارتند از:
توصيف کلاس پيچيدگی PTIME توسط فاگين
توصيف کلاس پيچيدگی PTIME توسط ايمرمن
