مروری بر نظریه ماشین‌های تورینگ، ماشین‌های تورینگ چند نواری و غیرقطعی (nondeterministic)، تز تورینگ-چرچ، مسائل و زبان‌های بازگشتی و به طور بازگشتی شمارا، تعریف مفاهیم زمان اجرا و فضای مصرفی یک الگوریتم (۲ جلسه)
مروری بر مسائل تصمیم ناپذیر، مساله توقف و انواع آن، قضیه رایس، روش قطری‌سازی (Diagonalization) (۲ جلسه)
مروری بر منطق گزاره‌ها و منطق مرتبه‌اول، مدل‌های حساب، قضایای صحت و تمامیت نظام استنتاجی منطق مرتبه‌اول، قضیه تصمیم‌ناپذیری منطق مرتبه‌اول، قضایای ناتمامیت گودل (۴ جلسه)
تعریف کلاس‌های پیچیدگی زمانی و فضایی در حالت کلی و قضایای اساسی ارتباط آن‌ها. قضیه سلسله مراتبی بودن (Hierarchy) و قضیه Gap در حوزه پیچیدگی زمانی و فضایی، مروری بر کلاس‌های زمانی P، NP، EXP و NEXP و کلاس‌های مکمل آن‌ها. مروری بر کلاس‌های فضایی L، NL، PSPACE، NPSPACE و کلاس‌های مکمل آن‌ها و ارتباط آن‌ها با کلاس‌های زمانی (۳ جلسه)
تعریف تقلیل (Reduction) و مسائلی که برای یک کلاس C-تمام (C-Complete) هستند. بررسی کلاس‌های مسایل P-Complete و NP-Complete. قضیه کوک-لوین و مباحث مرتبط با رابطه کلاس P و NP (۲ جلسه)
مروری بر برخی مسایل معروف NP-Complete (۲ جلسه)
کلاس coNP و مسائل توابع. کلاس PSPACE-Complete و مسایل مهم در آن (۱ جلسه)
کلاس‌های پیچیدگی الگوریتم‌های تصادفی، کلاس‌های RP، CoRP، ZPP، و BPP، پیچیدگی مداری (Circuit Complexity) (۳ جلسه)
الگوریتم‌های موازی، ساختار درونی کلاس P (۲ جلسه)
کلاس‌های پیچیدگی الگوریتم‌های تقریبی، حدود تقریب پذیری و تقریب ناپذیری (۲ جلسه)
رابطه نظریه‌های پیچیدگی و رمزنگاری. اثبات تعاملی (Interactive Proof) (۲ جلسه)
مباحث ویژه مانند نظریه پیچیدگی در حضور ماشین‌های تورینگ پیشگو (Oracle TM)، ماشین تورینگ تناوبی (Alternating TM)، نظریه پیچیدگی محاسبات کوانتومی (۳ جلسه)