نظریه محاسبات علوم ریاضیات

مقالهٔ اصلی: نظریه محاسبات

 

"نظریه محاسبات سعی دارد به این پرسش‌ها پاسخ دهد "که اساساً چه چیزی می‌تواند محاسبه شود و محاسبهٔ آن چقدر توان و منابع نیاز دارد.

 

 

 در تلاشی برای پاسخ گویی به پرسش اول، نظریه محاسبه‌پذیری ([computability theory]) بررسی می‌کند که چه مسائلی قابل حل هستند (از طریق نظریات مدل‌های پردازش). پاسخ دومین پرسش به نظریه پیچیدگی محاسباتی مرتبط می‌شود. این نظریه به زمان و فضای مورد نیاز برای رسیدن به پاسخ مطلوب در روش‌های مختلف پاسخگویی، می‌پردازد.

 

مسئله مشهور [["P=NP?"]]یکی مسائل حل نشده نظریه محاسبات است.