یکی از زیرشاخه‌های رشته علوم‌کامپیوتر بحث محاسبات و محاسبه‌پذیری به معنای عام هستش. این مسائل که نظریه محاسبه بهشون می‌پردازه چند مفهوم کلی دارن که در ادامه بهشون می‌پردازیم.
اولین مفهوم زمان اجرا هست. اگر به ماشین ورودی به طول n بدم ماکزیمم چقدر طول میکشه تا خروجی رو حساب کنه؟ معمولا جواب این سوال رو بر حسب تعداد گام‌های ماشین حساب می‌کنیم و جواب میتونه به شکل n^2 + 4n + 5 باشه، یا اشکال توانی و لگاریتمی داشته باشه.
تو نظریه محاسبه فرض ما کار کردن با اعداد بسیار بزرگه، و تو این اعداد بزرگترین عبارت چندجمله‌ای فقط اهمیت داره و ما همون رو در نظر می‌گیریم و با نماد O نشون می‌دهیم. مثلا برای ماشینی که رابطه‌اش n^2 + 4n+5 باشه می‌نویسیم عضو O(n^2) و میخوانیم از O یا اردر n به توان ۲ هست. واضحه که هر چقدر این O کمتر باشه ماشین سریعتره، فارغ از این که هر گام ماشین چقدر زمان میبره.
مفهوم دوم تصمیم‌پذیر یا معین بودن ماشین هست. ماشین‌های تصمیم پذیر ماشین‌هایی هستند که در هر لحظه حالت ماشین مشخص هست، در مقابل این‌ها ماشین‌های -فرضی- نامعینی وجود دارند که ماشین می‌تواند در هر لحظه چند وضعیت متفاوت داشته باشد.
بزارید با یک مثال توضیح بدم. فرض کنید می‌خواهید بهترین مسیر از خونه تا محل کار رو پیدا کنید و میدونید ۲ مسیر وجود داره. ماشین معین این مسیرها رو امتحان می‌کنه و میگه کدوم بهتره. ماشین نامعین مثل این می‌مونه که به ۲ نفر با سرعت یکسان بگه از خونه تا محل کار برن و هر کسی زودتر رسید مسیرش بهتره. حالا اگه ۴ مسیر باشه چی؟ خب به ۴ نفر میگه. اگه ۱۰۰۰۰۰۰ مسیر چی؟ به همون تعداد آدم. در واقع انگار موازی‌سازی داریم با این تفاوت که ماشین به اندازه ورودی بزرگ میشه.
مفهوم بعدی مفهوم کلاس‌های پیچیدگی هست که معروف‌ترین آن‌ها دو کلاس P و NP هستند. این کلاس‌ها سعی می‌کنند ماشین‌هایی که قدرت یکسان دارند رو دسته‌بندی کنند تا به ما دید بهتری از سختی حل اون‌ها بدن. کلاس‌های کوچکی هست مثلا کلاس O(n) که شامل تمام ماشین‌هایی میشه که زمانشون کمتر مساوی alpha*n باشه. یا کلاس O(2^n) که تعریف مشابهی داره. حالا اگر همه ماشین‌های معینی که زمانشون خطی هست - یعنی به فرم n^a هستند - رو توی یک کلاس بزاریم به این کلاس P می‌گوییم که مخفف Deterministicly Polynomial هست. در مقابل ماشین‌های نامعینی که خطی هستند را در کلاس NP که مخفف Nondererministicly Polynomial هست قرار می‌دهیم.
دقت کنید تا اینجا حرفی از مسئله زده نشده و فقط با ماشین‌ها کار داشتیم. اگر بخواهیم مسائل رو دسته‌بندی کنیم باید چکار کرد؟ تو این حالت بهترین ماشینی که مسئله رو حل می‌کنه رو نماد مسئله قرار می‌دهیم، مثلا برای مرتب‌سازی اعداد ماشین‌های زیادی وجود دارند اما می‌دانیم بهترین ماشین قدرتش از اردر nlogn هست. برای همین این مسئله را متعلق به کلاس P می‌نامیم.
چیزی که باید بهش توجه کرد اینه که کلاس P زیرمجموعه‌ای از کلاس NP هست، کافیه ماشین معینمون رو اسم نامعین روش بزاریم، دقت کنید که ماشین نامعین میتونه در لحظه تو چند حالت مختلف باشه ولی اجباری نداره! پس می‌دونیم که P زیرمجموعه NP هست، اما اگر بتونیم برعکسش رو اثبات کنیم مسائلی که هزینه محاسباتی سنگینی برایمان دارند رو می‌تونیم روی ماشین‌های خودمون سریعتر حل کنیم، اما این قضیه نه اثبات شده و نه رد شده.
مفهوم دیگه‌ای هست به اسم reduction که توسط اون مسائل رو به هم تبدیل می‌کنیم. فرض کنید دیوار برلین هنوز پابرجاست و شما در برلین شرقی قرار دارید. آدرسی دارید و باید مسیر اون رو پیدا کنید و ممکنه مسیری وجود نداشته باشه، مثلا اگر در برلین غربی باشه. شما اگر بتونید تاکسی بگیرید که شما رو به مقصد ببره مسیرش رو هم یاد می‌گیرید. پس مسئلتون رو reduce می‌کنید به پیدا کردن تاکسی. اگر پیدا بشه مسئله شما قابل حل هست و اگر مسئلتون قابل حل نباشه تاکسی پیدا نمیشه.
حالا فرض کنید من مسئله‌ای پیدا کردم که هر مسئله از کلاس NP قابل reduce شدن بهش باشه، و این reduce شدن خودش تو زمان خطی اتفاق بیقته(پیدا کردن تاکسی خطی باشه!!!) اون موقع این مسئله رو تو کلاس NP-Hard قرار می‌دهیم. تا این لحظه هیچ مسئله NP-Hard پیدا نشده که درجه سختی کمتری از NP داشته باشه، اما مسائل زیادی هستند که درجه سختی اون‌ها بسیار بیشتر باشه. برای همین این گروه که ساده‌ترین گروهی هستند که می‌توانند بقیه رو شبیه سازی کنن برامون خیلی جذابه: گروه NP-Complete که درواقع اشتراک NP و NP-Hard هست.
جالبی قضیه این‌جاست که اگر ما بتونیم یکی از این مسائل رو با درجات پایین‌تر حل کنیم، تمام مسائل گروه NP با اون درجه قابل حل خواهند بود و چیزی که بهش hierarchy collapse میگن اتفاق می‌افته و ما می‌تونیم گروه زیادی از مسائلی که برامون دردسر زیادی دارن رو تو زمان خیلی کم حل کنیم، مثل مسئله پیدا کردن کیلک تو گراف یا پیدا کردن مقدار دهی درست تو منطق.
تو پست بعدی سعی می‌کنم کمی در مورد محاسبات کوانتومی و اثرش روی مسائلی که گفتیم بپردازم.