Suatu masalah dianggap sulit secara inheren jika solusinya membutuhkan sumber daya yang signifikan, apa pun algoritma yang digunakan. Teori ini memformalkan intuisi ini, dengan memperkenalkan model perhitungan matematis untuk mempelajari masalah-masalah ini dan menghitung jumlah sumber daya yang diperlukan untuk menyelesaikannya, seperti waktu dan penyimpanan. Ukuran kompleksitas lain juga digunakan, seperti jumlah komunikasi (digunakan dalam kompleksitas komunikasi), jumlah gerbang dalam suatu sirkuit (digunakan dalam kompleksitas sirkuit) dan jumlah prosesor (digunakan dalam komputasi paralel). Salah satu peran teori kompleksitas komputasi adalah untuk menentukan batas praktis apa yang dapat dan tidak bisa dilakukan komputer.
Apa ukuran masalah komputasi yang secara luas mendefinisikan kesederhanaan yang melekat dari solusi?
jika solusinya membutuhkan sumber daya yang signifikan
jika solusinya membutuhkan sumber daya yang signifikan
Apa PRI
ukuran NNO
masalah NNO
komputasi NNO
yang PRR
secara PPO
luas ADJ
mendefinisikan VBT
kesederhanaan NNO
yang PRR
melekat VBI
dari PPO
solusi NNO
? PUN