=loyiha yechimi ~loyiha algoritmira

~barcha joriy ma'lumotlar variantlarini takrorlamasdan yechim topa olmaydi
~barcha joriy ma'lumotlar variantlarini qidirish bilan yechim topish mumkin
~barcha joriy ma'lumotlar variantlarining yarmini yoki undan ko'pini sanab o'tadigan yechimni topish mumkin
}

Polinom algoritmi - vaqt murakkabligi T(n) nimaga teng (n - masalaning o'lchami, p(n) n ning ko‘phadi)?.
{
=T(n)\=O(p(n))
~T(n)\=O(p(n))
~T(n)
~T(n)>O(p(n))
}

P \= NP masalasi bu:
{
=agar ba'zi bir savolga musbat javobni polinom vaqtida tekshirish mumkin bo'lsa, u holda bu savolga javobni ko'phad vaqtda topish mumkin.
~agar savolga manfiy javobni polinom vaqtida tekshirish mumkin bo'lsa, u holda bu savolga javobni ko'p nomli vaqtda topish mumkin
~agar biron bir savolga musbat javobni eksponensial vaqt ichida tekshirish mumkin bo'lsa, u holda bu savolga javobni polinom vaqtida topish mumkin.
~agar ba'zi bir savolga musbat javobni polinom vaqtida tekshirish mumkin bo'lsa, u holda bu savolga javobni eksponensial vaqt ichida topish mumkin.
}

Tyuring mashinasining o'z-o'zidan qo'llanilishini tan olish masalasi qanday talqin qilinadi?
{
=algoritm bo'yicha qaror qabul qilib bo'lmaydi
~algoritmik jihatdan hal qilinishi mumkin
~masalalarning P sinfiga kiradi
~NP masalalari sinfiga kiradi
}

Tyuring mashinasining o'z-o'zidan qo'llanilishi masalasi qanday tuzilgan?
{
=Turing mashinasi o'z kodiga ega
~Tyuring mashinasi tashqi alifbodagi har qanday so'z uchun qo'llaniladi
~Turing mashinasi ichki alifbodagi har qanday so'z uchun qo'llaniladi
~Turing mashinasi tashqi alifbodagi so'zlarning sanab o'tiladigan to'plamiga nisbatan qo'llaniladi