1. Algoritm murakkabligini statik va dinamik o‘lchovlari. Vaqt va xotira hajimi bo‘yicha qiyinchiliklar

K - amalga oshirish imkoniyati .
K-qoniqarliligi CNFga kiritilgan har qanday bandda ko'pi bilan K mantiqiy o'zgaruvchilar mavjudligini anglatadi.
Minimal holat K = 3. CNFda ifodalangan mantiqiy funktsiya uchun polinom vaqtida funktsiyani topish mumkin E * (x2) har bir bandda ko'pi bilan uchta o'zgaruvchini o'z ichiga oladi. Keyin E amalga oshirish mumkin bo'lsa E *.
E* (x1 , x2 ,…, xn) ® E* (xi)
Buning uchun band tartibini kamaytirish usuli qo'llaniladi
(a1 Ú a2 Ú … Ú ak)=(a1 Ú a2 Ú z) Ù (a3 Ú a4 Ú … Ú ak Ú )
Iterativ parchalanish jarayonini qo'llash orqali olish mumkin E *.
Yechim algoritmini toping E * funksiyalarga qaraganda oddiyroq E... Ammo shu bilan birga, maqsadga muvofiqligini isbotladi E *, biz asl funktsiyaning qoniqarliligini isbotlaymiz E.
Maxsus holat: K = 2 uchun funktsiya E R ga kiritilgan.
NP-sinf muammolariga misollar ham grafik muammolar :
1) Yo'naltirilmagan grafikning kliklarining maksimalini aniqlash (NP-qiyin masala).
2) To'liq subgrafani aniqlash masalasi (NP-to'liq muammo).
3) Yo'naltirilmagan grafik uchun L kardinallikning cho'qqi qoplamasini aniqlash (NP-to'liq muammo).
4) Yo'naltirilmagan grafikning maksimal cho'qqi qoplamalarini aniqlash (NP-qiyin masala).
5) Grafik uchun Gamilton siklining mavjudligini aniqlash masalasi (NP-to'liq masala).
6) Sayohatchi sotuvchi muammosi: Har bir cho'qqida bitta hodisa bilan grafik bo'ylab optimal harakatni aniqlash (NP-qiyin muammo).
7) Rejalashtirish muammosi (NP-to'liq muammo).
2.6 Algoritmik yechilmaydigan masalalar
Muammolarni baham ko'ring yolg'iz va katta.
Masalan:
5 + 7 =? Yagona muammo.
x + y =? Katta muammo.
Paradoksal bo'lgan ob'ektlarni olish yoki paradoksal ob'ektlar mavjud bo'lgan muammolarni hal qilish algoritmlari tubdan hal qilib bo'lmaydigan bo'lishi kerak.
Masalan, paradokslar:
1-misol:
Hilbertning 10-muammosi.
D. Gilbert 1901 yilda diofant tenglamalarini yechishda quyidagi masalani ilgari suradi:
Ixtiyoriy Diofant tenglamasi uchun qandaydir butun son yechimini aniqlaydigan algoritmni toping.
F(x, y, …)=0
Bu noma'lumlar uchun butun ko'rsatkichli va butun son koeffitsientli polinom
anxn + an-1xn-1 +… + a2x2 + a1x + a0 = 0
Yuqoridagi tenglama uchun ma'lum bir yechim mavjud bo'lib, u har bir butun son ildizidan iborat xi bo'luvchi hisoblanadi a0 ... Qayerda a0 asosiy omillarga ajrating va har bir omilni ildizga muvofiqligini tekshiring.
1970 yilda leningradlik matematik Yu.Matiyasevich Diofant tenglamasini umumiy shaklda yechishning algoritmik imkonsizligini matematik tarzda isbotladi.
2-misol:
Ferma teoremasi:
Bunday butun sonlar mavjud emas a, b, s, n (n>2) buning uchun tenglik
a + bn = cn
Bu teorema ko'p qiymatlar uchun isbotlangan n va maxsus holatlar uchun tekshiriladi, lekin teoremaning umumiy isboti hali yaratilmagan.
3-misol:
Goldbax muammosi.
X. Xolbax 1742 yilda Eylerga yo‘llagan maktubida muammoni shunday shakllantirgan:
Har bir butun sonni isbotlang N³ 6 uchta tub sonning yig'indisi sifatida ifodalanishi mumkin
N= a+ b+ c
Bu shuni anglatadiki, siz har qanday butun songa ruxsat beradigan algoritmni topishingiz kerak N³ 6 kamida bitta parchalanishni uchta oddiy atamaga toping.
Eyler bu muammoni tez-tez hal qilishni taklif qildi: hatto uchun N bu muammo echilishi mumkin va ikkita oddiy atamaga parchalanishga teng.
I. Vinogradov 1937 yilda buni g'alati ekanligini isbotladi N uchta oddiy atamani topish mumkin, lekin juft sonlar uchun yechim hali topilmagan.
O (1) - Dasturdagi amallarning aksariyati faqat bir marta yoki bir necha marta bajariladi. Doimiy murakkablik algoritmlari. Ma'lumotlar hajmidan qat'i nazar, har doim bir xil vaqtni talab qiladigan har qanday algoritm doimiy murakkablik.