পরিগণনামূলক জটিলতা তত্ত্ব

পরিগণনামূলক জটিলতা তত্ত্ব (ইংরেজি: Computational complexity theory) কম্পিউটার বিজ্ঞানের পরিগণনার তত্ত্বের একটি শাখা যেখানে অ্যালগোরিদমসমূহের scalability তথা বড় মাপের কাজ করার যোগ্যতা সম্পর্কে আলোচনা করা হয়। অ্যালগোরিদমের প্রবিষ্ট বা ইনপুটের আকার বাড়ার সাথে সাথে সেটির জন্য প্রয়োজনীয় সময় ও স্মৃতি বা মেমরির আকার কীরকম বেড়ে যায়, সে সম্পর্কিত বাস্তব সীমারেখা নির্ধারণ করা এই তত্ত্বের আলোচ্য।

একটি সিদ্ধান্তের সমস্যার কোন ইনপুটে কেবল দুটি সম্ভাব্য আউটপুট আছে, হ্যাঁ বা না (অথবা পর্যায়ক্রমে 1 বা 0)