To'g'ri murakkablik funktsiyasi - Proper complexity function

A to'g'ri murakkablik funktsiyasi funktsiya f xaritalash a tabiiy son quyidagicha tabiiy songa:

• f kamaytirilmaydi;
• mavjud a k-tarmoq Turing mashinasi M shunday uzunlikning har qanday kiritilishida n, M O dan keyin to'xtaydi (n + f(n)) qadamlar, O (f(n)) bo'shliq va chiqishlar f(n) ketma-ket bo'shliqlar.

Agar f va g Ikkala murakkablik funktsiyalari, keyin f + g, fgva 2^f, shuningdek, murakkablikning to'g'ri funktsiyalari.

Shunga o'xshash tushunchalar halol funktsiyani, kosmosda tuziladigan funktsiya va vaqtni tuzadigan funktsiya.

^[1]

Adabiyotlar