مقالهٔ اصلی: نظریه محاسبات
"نظریه محاسبات سعی دارد به این پرسش‌ها پاسخ دهد "که اساساً چه چیزی می‌تواند محاسبه شود و محاسبهٔ آن چقدر توان و منابع نیاز دارد.
در تلاشی برای پاسخ گویی به پرسش اول، نظریه محاسبه‌پذیری ([computability theory]) بررسی می‌کند که چه مسائلی قابل حل هستند (از طریق نظریات مدل‌های پردازش). پاسخ دومین پرسش به نظریه پیچیدگی محاسباتی مرتبط میشود. این نظریه به زمان و فضای مورد نیاز برای رسیدن به پاسخ مطلوب در روش‌های مختلف پاسخگویی، می‌پردازد.
مسئله مشهور [["P=NP?"]]یکی مسائل حل نشده نظریه محاسبات است.
ادامه مطلب