Sebuah masalah dianggap sebagai kesulitan inheren jika solusi membutuhkan sumber daya yang signifikan, apa pun algoritma yang digunakan. Teori ini memformalkan intuisi ini, dengan memperkenalkan model matematika komputasi untuk mempelajari masalah-masalah ini dan mengukur jumlah sumber daya yang diperlukan untuk menyelesaikannya, seperti waktu dan penyimpanan. Langkah kompleks lainnya juga digunakan, seperti jumlah komunikasi (digunakan dalam kompleksitas komunikasi), jumlah gerbang dalam sirkuit (digunakan dalam kompleksitas sirkuit) dan jumlah prosesor (digunakan dalam komputasi paralel). Salah satu peran dari teori komputasi kompleksitas adalah untuk menentukan batas praktis pada apa yang komputer bisa dan tidak bisa lakukan.
Metode apa yang tidak digunakan untuk menilai secara intuitif atau mengukur jumlah sumber daya yang diperlukan untuk memecahkan masalah komputasi?
model matematika komputasi