«amaliy matematika va informatika» kafedrasi «Algoritmlar nazariyasi» fanidan Mustaqil ish

Qatʻiy va kuchsiz polinom vaqti

Baʻzi kontekstlarda, ayniqsa optimallashtirishda algoritmlar bilan ajralib turadi qatʻiy polinom vaqti va zaif polinom vaqt... Ushbu ikkita tushuncha faqat butun sonlardan tashkil topgan kirishga tegishli.

Aritmetik hisoblash modelida qatʻiy polinom vaqti aniqlangan. Ushbu modelda operandlar uzunligidan qatʻi nazar, bajarilish birligi sifatida asosiy arifmetik amallar (qoʻshish, ayirish, koʻpaytirish, boʻlish va taqqoslash) olinadi. Algoritm qatʻiy polinom vaqtida ishlaydi, agar

1. 
   arifmetik hisoblash modelidagi amallar soni kirish oqimidagi butun sonlar sonidagi polinom bilan cheklangan va
   
2. 
   algoritm tomonidan ishlatiladigan xotira kirish kattaliklarida polinom bilan chegaralangan.
   

Ushbu ikkita xususiyatga ega boʻlgan har qanday algoritm arifmetik amallarni Tyuring mashinasida arifmetik amallarni bajarish uchun tegishli algoritmlar bilan almashtirish orqali koʻp polinom vaqt algoritmiga tushirilishi mumkin. Agar yuqoridagi talablarning ikkinchisi bajarilmasa, bu endi toʻgʻri boʻlmaydi. Butun sonni hisobga olsak (u Tyuring mashinasida n ga mutanosib xotirani egallaydi), uni takroriy eksponentatsiya yordamida n ta amal bilan hisoblash mumkin. Biroq, tasvirlash uchun ishlatiladigan xotira 2 2 n (\\ displaystyle 2 ^ (2 ^ (n)))), bilan mutanosib 2 n (\\ displaystyle 2 ^ (n))va bu polinomga emas, balki kirish uchun ishlatiladigan xotiraga bogʻliq. Demak - Turing mashinasida bu hisob-kitoblarni polinom vaqtida bajarish mumkin emas, ammo arifmetik amallarning polinom sonini bajarish mumkin.

Aksincha, Turing mashinasining pogʻonalari sonida ishlaydigan, binar kodlangan kirish polinom uzunligi bilan cheklangan, ammo arifmetik amallar sonida ishlamaydigan algoritmlar mavjud. kirish. Evklidning ikkita butun sonning eng katta umumiy boʻluvchisini hisoblash algoritmi bunga misoldir. Ikki butun son uchun a (\\ displaystyle a) va b (\\ displaystyle b) algoritmning ishlash muddati cheklangan O ((log-a + log-b) 2) (\\ displaystyle O ((\\ log \\ a + \\ log \\ b) ^ (2))) Turing mashinasining qadamlari. Ushbu raqam raqamlarning ikkilik tasviri hajmining polinomidir a (\\ displaystyle a) va b (\\ displaystyle b), bu taxminan sifatida ifodalanishi mumkin log \u2061 a + log \u2061 b (\\ displaystyle \\ log \\ a + \\ log \\ b)... Shu bilan birga, arifmetik amallar sonini kirishdagi tamsayılar soni bilan cheklab boʻlmaydi (bu holda doimiy boʻladi - kirishda faqat ikkita raqam mavjud). Ushbu eslatmani hisobga olgan holda, algoritm qatʻiy polinom vaqtida ishlamaydi. Algoritmning haqiqiy ishlash vaqti qiymatlarga bogʻliq a (\\ displaystyle a) va b (\\ displaystyle b), faqat kirishdagi butun sonlar soni emas. Agar algoritm polinom vaqtida ishlaydi, lekin qatʻiy polinom vaqtida emas boʻlsa, u ishlaydi deyiladi zaif polinom vaqti ... Zaif polinomial algoritm maʻlum, ammo qatʻiy polinomial algoritm maʻlum boʻlmagan masalaning taniqli misoli bu chiziqli dasturlashdir. Zaif polinom vaqtni psevdo polinom vaqt bilan chalkashtirmaslik kerak.