پیشینه

نظریه محاسبات

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

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