=loyiha yechimi ~loyiha algoritmira

}


NP-masala uchun qaysi ta'rif to'g'ri (chiziqli bo'lmagan polinom va chiziqli bo'lmagan polinom):
{
=yechimi polinom vaqtida deterministik Tyuring mashinasida tekshirilishi mumkin bo'lgan masala
~Polinom bo'lmagan vaqtdaTyuring mashinasida (NTM) yechib bo'lmaydigan masalalar sinfi
~polinom vaqtida deterministik Tyuring mashinasida (DTM) yechish mumkin bo'lgan masalalar sinfi..
~To'g'ri javob yo'q
}

Qanday masala NP-to'liq masala deb nomlanadi&
{
=agar u NP sinfiga tegishli bo'lsa va NP dan boshqa har qanday masala polinom vaqtda unga keltiriladi
~agar u NP va NP-to'liq sinfiga tegishli bo'lsa. Ba'zi NP masalalari.
~agar u NP-to'liq masala bo'lsa, u polinom vaqtida C ga kamayadi.
~To'g'ri javob yo'q
}

NP-oraliq masala deb ataladi
{
=agar u NP va NP-to'liq sinfiga tegishli bo'lsa.
~agar u NP sinfiga tegishli bo'lsa va NP ning boshqa har qanday vazifasi ko'p nomli vaqt ichida unga qisqartirilsa
~agar u NP-to'liq masala bo'lsa, u polinom vaqtida C ga kamayadi (algoritmik qaytarilish Kuk).
~To'g'ri javob yo'q
}

C Masala NP-qiyin deb ataladi, agar
{
=u NP-to'liq masala bo'lsa va polinom vaqtida C ga keltirilsa
~u NP sinfiga tegishli bo'lsa va NP ning boshqa har qanday vazifasi ko'p nomli vaqt ichida unga qisqartirilsa
~u NP va NP-to'liq sinfiga tegishli bo'lsa. Ba'zi NP masalalari (graflarning izomorfizmi, mantiqiy funktsiyani minimallashtirish, ...) uchun (hozirda) NP-to'liq sinfga tegishli ekanligi isbotlanmagan.
~To'g'ri javob yo'q
}

Raqamli tartiblash algoritmining hisoblash murakkabligi qanday?
{
=Chiziqli
~Kvadratik