Log-space hisoblash funktsiyasi - Log-space computable function

A log-space hisoblash funktsiyasi funktsiya ${ displaystyle f colon Sigma ^ { ast} rightarrow Sigma ^ { ast}}$ bu faqat talab qiladi ${ displaystyle O ( log n)}$ hisoblash uchun xotira (ushbu cheklash chiqish hajmiga taalluqli emas). Hisoblash odatda a yordamida amalga oshiriladi kosmik transduser.

Joyni qisqartirish

Hisoblash mumkin bo'lgan log funktsiyalari uchun asosiy foydalanish bo'shliqni qisqartirish. Bu faqat bitta logaritmik bo'shliqdan foydalanib, bitta masalaning nusxasini boshqa masalaning misoliga aylantirish vositasidir.

Log-space hisoblanadigan funktsiyalariga misollar

• Muammoni konvertatsiya qilish a deterministik bo'lmagan Turing mashinasi bu qaror qiladi til A log-bo'shliqda ST-ulanish.^[1]

Izohlar

Adabiyotlar

• Sipser, Maykl (2006), Hisoblash nazariyasiga kirish, O'qishni to'xtatish, ISBN  978-0-619-21764-8.

P ≟ NP

Bu nazariy informatika - tegishli maqola a naycha. Siz Vikipediyaga yordam berishingiz mumkin uni kengaytirish.