Raqamli kutubxona Kibernetikadan matematik masalalar

§1P dan matritsalar tomonidan yaratilgan chiziqli pastki bo'shliqlar.
Biz juftlarni o'z ichiga olmaydigan matritsalar to'plami bilan belgilaymiz
bir xil yoki qarama-qarshi chiziqlar. Ch1n deyarli barchasini o'z ichiga olishi aniq
matritsalar, ya'ni | ®n | ~ | ®n |, rc -> 00. Ch1n to'plamini sinflarga ajratamiz
ekvivalentligi quyidagicha. Bir sinfga biz matritsalarni kiritamiz,
bir-biridan satrlarni almashtirish va almashtirish operatsiyalari orqali olinadi
qarama-qarshi chiziqlar. Keyin har bir sinfda aniq p \ 2 ° bo'ladi
matritsalar. Bir xil ekvivalentlik sinfidagi barcha matritsalar ekanligi aniq
bir xil pastki bo'shliqni yarating. Va deyarli barcha matritsalar ekanligidan
chiziqli korpusda satrlardan boshqa hech qanday (± 1) -vektor mavjud emas
matritsa va ularning qarama-qarshiligi, shundan kelib chiqadiki, ularning soni har xil
pastki bo'shliqlar asimptotik ravishda ekvivalentlik sinflari soniga to'g'ri keladi;
ya'ni 2pn / (p \ 2p) ga teng. Bu teoremaning tasdiqlanishini anglatadi (qarang
tuzatish uchun qo'shimcha).
(6) dagi yuqori chegarani hisobga olgan holda, biz olamiz
Nn = 2n2 (1-0 (1)), n -> oo.
2. Berilgan kardinallikning chegara to'plamlari soni. Shu qatorda; shu bilan birga
chegara funktsiyalarining umumiy soni Nn ni baholash qiziqish uyg'otadi
Nn (M) soni uchun hisob-kitoblarni olish - berilgan bilan chegara funktsiyalari
birlar soni (nol) M yoki boshqacha qilib aytganda, chegara soni uchun
kardinallik to'plamlari M. Giper tekisliklarning ajralish holatlarida e'tibor bering

31-bet

34
Yu, A. Zuev
Endagi umumiy pozitsiya nuqtalari, bizda bunday muammodan
rad etish, chunki umumiy nuqtalarning o'zboshimchalik to'plamining kardinalligi
pozitsiya chiziqli sonini tekshirish oson bo'lganidek aniqlamaydi
berilgan quvvatning uzilishlari [66]. Ostona mantiqda esa, bu taxminlar
chegara to'plamining batafsil tavsifi
funktsiyalari. 2-bandning 7-bandida ko'rib chiqilgan qisman tartib nuqtai nazaridan
Nn (M) - balandlikdagi elementlarning soni M. Maxsus ma'no o'xshash
ballar chegara ko'rsatkichlarini o'rganish orqali olinadi. Mana bu rol
berilgan kardinallikning chegara to'plamlari elementarga o'xshaydi
d.n nazariyasida berilgan darajali birikmalar. f.
Nn (M) ni baholash muammosi birinchi marta muallif tomonidan ko'rib chiqilgan va
Lipkin [11]. Olingan hisob-kitoblar keyinchalik [12] va da mustahkamlandi
[16] da yakuniy shaklini oldi. Teoremaning barcha shartlarida c harfi
qandaydir doimiyni bildiradi.
Teorema 18. Berilgan o'zgarish xarakteri uchun n ortishi bilan
M (n) log Nn (M) uchun quyidagi asimptotiklar amal qiladi:
1) agar M = o (n) 9 bo'lsa log Nn (M) ~ n;
2) agar M = c / z (1 + o (1)), u holda \ ogNn (M) ~ gg (c log (1 + 1 / c) +
+ log (1 + s) + 1);
3) agar M = a (n) w a log a (n) = o (log / r), log Nn (M) ~
~ nloga {n);
4) agar J == / rc + 0 (1), c> 1 bo'lsa, logNn (M) ~ (c - l) nlog n;
5) agar M = 2Hn \ P (? Z) = o (? Z), log Nn (M) ~ $ {n) u
6) agar M - * 2cr (1h "0 (1)), 0 Isbot. Teoremaning 1) -6) asimptotiklarining har biri
yuqori va pastki asimptotik mos kelishini olish bilan isbotlanadi
log Nn (M) uchun hisob-kitoblar. Barcha yuqori chegaralar hisoblash yo'li bilan olinadi
turli Chow vektorlari soni. Xuddi shu past baholarni olish uchun
har bir holatda maxsus usul qo'llaniladi: 1) -3) bu
ostonaning konstruktiv qurilishi o'zini o'zi belgilaydi; 4) -5) da - qurilish
chegara to'plamlarini aniqlovchi chiziqli tengsizliklar to'plami
berilgan kuch; 6 da) yordamida konstruktiv bo'lmagan usul hisoblanadi
ehtimolli fikrlash orqali olingan asimptotikalar (7).
Keling, yuqori baholardan boshlaylik. B 6) bu juda oddiy bo'lib chiqadi.
(n + 1) o'lchovli Chow vektorining har bir koordinatasi S (A) butun sondir
dan ortiq bo'lmagan manfiy son \ A I. Shuning uchun 6-holda)
ko'pi bilan 2 ta cn (1 + 0 (1)) (r + 1) aniq Chow vektorlari mavjud, bu erdan
shundan kelib chiqadiki, log Nn (M) 1) -5), biz texnik jihatdan eng qiyin 2) holatga e'tibor qaratamiz.
Bu erda qo'llaniladigan usullar yuqori qismini olish uchun etarli
qolgan barcha holatlarda taxminlar.
Kardinallik cn A o'q bilan o'rnatilgan monoton pol belgilansin
{> 0 bilan (1) tengsizlik bilan berilgan. a { ga ko'ra koeffitsientlarni tartibga keltiramiz
Shunday qilib, biz k raqamini tanlaymiz
aik-i “b aik ^ b, a \ k + aik + 1> b. ^ ^ cni dan k <21 cn kelib chiqadi. Bo'lsin
/ == "{1, 2, ..., n), 1 \ = Ui, ..., ik}, Iq = {ik + 1, ..In). Keyin bor
A ga tegishli cho'qqilar / -o da bir nechta birlik koordinatasiga ega bo'lishi mumkin emas.
Demak, A to‘plamning Chou vektori (^ 4) = (^ 0, si, ..., sn) uchun bizda
2 ^ cn. Cn dan ortiq bir xil narsalarni joylashtirish mumkin emas
iei0
ft - \ - cn \
t dan ortiq turli qutilar (% I yo'llar (qarang [39]). Shuning uchun
Chow vektorining turli / o-parchalari ko'pi bilan n ^ bo'lishi mumkin
^ ^ ~ L Cn'j * Turli xil / i-parchalar soni oshmaydi

32-bet

Mantiqiy funksiyalarning chegaraviy funksiyalari va chegaraviy ko‘rinishlari 35
{cnfVcn. Va / ichiga / o va 1 \ bo'linish usullari soni oshmaydi
* 2G (/) <2 / euniV ™.
3 = 0
Shuning uchun, monoton polning iV® (cn) soni uchun kardinallik to'plamlari
bizda bor
gU ™ (n + cn \
1o
g Nn (cn) n (s log (1 + 1 / s) - {- log (1 + s)).
Nn (cn) <2nNn (cn) ekanligini o'qib, olamiz
log Nn (cn) ^ rc (tiqilib qolish (l + 1 / c) + log (1 + c) + 1).
Keling, quyi chegaralarga o'tamiz. Holat 1) aniq. Keling, ko'rsataylik
2) va 3) holatlar uchun 2-bandning 6-bandi, 6-bandi yordamida biz tuzamiz
kerakli miqdordagi monoton chegara to'plamlari joylashgan
ikkinchi qatlam ichida va asosan barcha koordinatalarga bog'liq. Uchun
aniqlik, biz 2-holatni ko'rib chiqamiz). Avval yoqamiz
chegara to'plami A nol tepalikdir. Keyin, birinchi bosqichda biz tanlaymiz
n koordinatadan mn \ koordinatalar va A V ga birinchi qavatning uchlarini kiriting,
tanlangan koordinatalarni yagona koordinatalar sifatida olish. Qolgan cho'qqilar
birinchi qavatni A dan tashqarida qoldiramiz. Ikkinchi bosqichda biz mn \ koordinatalaridan tanlaymiz,
birinchi qadamda olingan, m2 +1 koordinatalari va ulardan birini belgilang.
Yana A m belgilangan va tanlangan belgilanmagan koordinatalardan biri. Davom etilmoqda
shunday qilib, tanlangan va belgilanmaganlarning y ~ th bosqichida
koordinatalarning oldingi bosqichida biz mn, + 1 koordinatalarini tanlaymiz, ulardan birini belgilaymiz
ularni va 1 belgilangan va ikkinchi qavat cho'qqilarining rrij
tanlangan belgilanmagan koordinatalardan biri, biz A.ga kiritish k
h
qadamlar, biz 1 + 2 mj kardinallik A monotonli pol to'plamini olamiz>
j = i
qaysi mn \> W2 + I uchun asosan barcha koordinatalarga bog'liq. Shunday qilib
yo'l bilan olish mumkin
(wj (m2 + l) (HO2 + 1) • • • (mk + 1) =
- -. (yigirma)
(n - mx) \ K ~ m2 - 1)! ... (mk_g - - 1)! mh \
chegara to'plamlari.
Endi qurilish jarayonini to'liq aniqlash uchun biz qo'yamiz
rrij = ^ [uh}], bu erda q = c / (c + 1) va k qiymati shunday o'rnatiladi
jarayon tabiiy ravishda to'xtaydi. Keyin
\ A \ = 1 + [u \ + [u2] + ... + [nqk] ~ cn,
va quyidagi (20) dan (batafsilroq [12] ga qarang), sonning logarifmi
tuzilgan monoton chegara to'plamlarining asimptotik jihatdan teng
n (c \ og (i + 1 / c) + log (l + c)), bu 2 da asimptotikani isbotlaydi).
4) va 5) dagi pastki chegaralar konstruktiv tomonidan isbotlangan
chegara o'zgarishi usuli bilan chiziqli tengsizliklar to'plamini qurish orqali,
(6) da pastki chegarani olgan (2-band, 3-bandga qarang). Agar Af <2 ", keyin
kardinallikning har bir pol to'plami uchun m, bu erda 0 subkubida xn = 0, bu a miqdorini mos tanlash yordamida mumkin
xn - 1 subkubida M - m kardinallik chegarasi to'plamini oling, shuning uchun
shunday qilib, butun kubda o'rnatilgan polning kardinalligi M. Po ga teng

33-bet

36
bu M = 5 2P-1 uchun bizda mavjud
NS. A. ZUEV
(21)
m
Nn (M)> S Nn ^ (m).
7P = 0
M ^ 2n “ft uchun (21) dan foydalanib, biz olishimiz mumkin
k-m
Nn m> T | UP- 2 ^ n- (22)
'' 7P = 0
k = n -] logM ni belgilash [va bu holda Nn-h (M)> 1 ekanligini hisobga olgan holda,
Biz (22) dan kerakli pastki asimptotik baholarni olamiz
holatlar 4) va 5).
Keling, 6-holatda pastki chegaraga murojaat qilaylik). log M cn.
I = [cn] qo‘yib, (21) dan foydalanib, biz bor
m
Nn (m)> 2 Nn. (Te)> (2 *).
7P = 0
Endi - I - 1 ni olib, (22) dan foydalanib, biz olamiz
2Z (n — r — 2)
771-0
2)!
Ammo Ni (2l ~ l) soni o'z-o'zidan ikkilamchi chegara soniga to'g'ri keladi
funksiyalar va 15-teorema bo'yicha log Nt {2l ~ l) ~ I2. Shuning uchun log Nn (M) ^ l (n - Z) +
+12 ~ cn2. 18-teorema isbotlangan.
3. Og'irlik omillarining kattaligi. Geometrik chegara
(1) funksiya kichik to‘plamni ajratuvchi giper tekislik orqali berilgan
/ ~ Ch0) pastki to'plamdagi giperkubning uchlari Yuqorida aytib o'tilganidek,
giperplanning holatida engil o'zgarish, bu ajratish har doim
kub cho'qqilarining birortasi yotmasa, qattiq bo'lishi mumkin
giperplanlar. Bunday holatda, tabiiyki, qanchalik kattaligi haqida savol tug'iladi
giper tekislikdan unga eng yaqin cho'qqigacha bo'lgan masofa bo'lishi mumkin
erishish. Boshqacha qilib aytganda, vazifa miqdorni taxmin qilishdir
p (/) = maksimal min J (23)
Maksimal bu erda giperplanning barcha pozitsiyalarida olinadi,
giperkubning uchlarini belgilangan ajratishni amalga oshirish. Bundan tashqari, siz,
Muayyan funktsiyadan abstraktsiya qilish, qiymatni ko'rib chiqing
P (n) = min p (/),
bu erda minimal n o'zgaruvchining barcha chegara funktsiyalari uchun olinadi.
Chegara funktsiyasini texnik amalga oshirishda / asosida
ba'zi jismoniy printsip bo'yicha (qarang [2, 86]), tufayli
og'irlik va chegaraga mos keladigan jismoniy miqdorlarning muqarrar o'zgarishi;
giperplane biroz tebranadi va uning holatidagi o'zgarishlar bo'lmaydi
u amalga oshiradigan funktsiyaga faqat etarli bo'lsa ta'sir qiladi
p (/) ning katta qiymati. p (n) miqdori sifatida qaralishi mumkin
umuman bo'sag'a mantig'ining barqarorligining xarakteristikasi.
Biroq, an'anaga ko'ra, muammo chegara mantiqida ko'rib chiqiladi
biroz boshqacha tarzda qo'yiladi. sistema a = ab ..., an va T deyiladi
f chegara funksiyasining normallashtirilgan realizatsiyasi: {0, 1) n -> - {0, 1) agar
(a, xXG-1, x ^ GH0),
(a, x)> T, xe / - '(1). (J ±)
normallashtirilgan amalga oshirish bilan, shuning uchun, bir

34-bet

BOSH FUNKSIYALARI VA BUL FUNKSIYALARNING BOSHQA FUNKSIYALARI 37
o'q va bitta o'rtasidagi chiziqli funktsional boshqa "bo'shliq"
funksiya qiymatlari.
Agar chegara funktsiyasi / (4) / ko'rinishida berilgan bo'lsa: {- 1, 1} n {- 1, 1},
keyin uning normallashtirilgan amalga oshirilishi quyidagi shaklni oladi:
(a, y) <- 1, Y ^ / _ 1 (-1)>, „r.
(a, y) S * l, ue / -> (1), °
bu erda y = (1, yn, yn), a = (o0, al .. an) va a va an qiymatlari
NS
bu erda (24) dagi kabi va a0 = 2 a \ -} - 1 - 2T.
i = i
Eshik mantiqida normallashtirilgan amalga oshirish uchun
vazn koeffitsientlarini minimallashtirish muammosi ko'rib chiqiladi. Minimallashtirish sifatida
NS
(25) ni amalga oshirishda funktsiyaning 2 \ ai \ qiymatini olamiz,
i == o
va masala chiziqli dasturlash usullari bilan yechiladi.
Eshik funktsiyasining har qanday butun sonli bajarilishi uning hisoblanadi
standartlashtirilgan amalga oshirish. Oltmishinchi yillarning boshlarida
har qanday chegara funktsiyasi uchun mavjud degan gipoteza mavjud edi
butun son minimal amalga oshirish. Biroq, bunday emasligi ma'lum bo'ldi. Birinchidan
9 ta o'zgaruvchidan iborat funksiya misoli, yagona minimal
uning amalga oshirilishi kasr og'irliklarini o'z ichiga oladi Uillis [114] tomonidan qurilgan.
Keyinchalik ma'lum bo'ldiki, bunday misollar allaqachon funktsiyalar uchun topilgan
8 ta o‘zgaruvchiga [85].
Chow parametrlari kabi butun sonni amalga oshirish imkonini beradi
chegara funksiyalarini kodlash. Biroq, bu erda, parametrlardan farqli o'laroq
Chow, chegara to'plamining xaritasini aniq tanlash qiyin
og'irliklar to'plamiga aylanadi, chunki turli xil butun sonlar to'plami
amalga oshirish bo'lishi mumkin va shu bilan birga minimal, bir xil
chegara funktsiyasi. Lekin butun son og'irliklari bilan kodlash
bilan erishib bo'lmaydigan funksiya qiymatlarini hisoblashni osonlashtiradi
Chow parametrlaridan foydalanish. C, bunday kodlashning noto'g'riligi bilan belgilanadi
ishlatiladigan butun sonlarning maksimal mutlaq qiymati
amalga oshirishlar.
Bo'lsin
M (/) == min max | a%\,
a
bu erda minimal funktsiyaning barcha amalga oshirilishi (24) uchun olinadi /. Bo'lsin,
Keyinchalik,
M (n) = maksimal M (/),
1
bu erda maksimal n o'zgaruvchining barcha chegara funktsiyalari uchun olinadi.
Butun sonni amalga oshirish uchun o'xshash qiymatlar bilan belgilanadi
mos ravishda L / c (/) va Mt (n) orqali. Ko'rinib turibdiki, M (n) '<
NS
r - 1
n o'zgaruvchining shox funksiyalarini hisobga olgan holda sanab o'tish mumkin
(2Mts (n) + 1) (2nMts (n) + 1) og'irlik va chegaralarning turli kombinatsiyalari.
Demak, biz M1X (n) ni pastdan taxmin qilishimiz mumkin. Nisbatdan
(2mts (ga) + 1) ”(2mts (ga) + 1)> Nn = 2p '(1- ° (1))
kerak
nlogMc (n) ^> n2,
log L / q (m) ^ m.
Bundan tashqari, deyarli barcha chegara funktsiyalari uchun /,
LH, (/)> 2n <1-0 (1)).
(26)

35-bet

38
Yu. A. Zuev
M (n) va Mc (n) dagi miqdorlarning o'sish sur'atlarini aniqlash masalasi
chegara mantiqiga katta ahamiyat berildi. Oltmishinchi yillarning boshi
yillar davomida bir qator mualliflar funktsiyalarning namunalarini konstruktiv tarzda qurdilar
n o'zgaruvchida, uchun
qaysi M (f) = Mc (1) X2n. Bular
talab
sezilarli zukkolik
dizaynlar va tegishli
bibliografik manbalar
[2, 86] da topish mumkin.
Elementar tomonidan olingan
quvvatga asoslangan baholash
(26) biroz zaifroq, lekin
u deyarli hamma uchun amal qiladi
funktsiyalari, tavsifi
shunday xatti-harakat
Mn (f) odatiy holatda.
Keling, qanday qilib buni ko'rsatamiz
geometrik
kuchni o'zgartiradigan fikrlash
uchun nost usuli
uzluksiz holatda, mumkin
taxminning to'g'riligini isbotlash
(26) va M (f) uchun.
Teorema 19. M (n) uchun
adolatli baho
] ogM (ri) ^ n, n - * oo?
va M (f) qiymatlari deyarli barcha chegara funktsiyalari uchun juda katta /.
Isbot. Og'irliklarning (n + 1) - o'lchovli fazosida
(giper tekisliklardan hosil bo'lgan mos konuslar mavjud (8). (8-rasmga qarang,
Bu erda n = 1 holi keltirilgan.) Biz vazn vektorlarini normallashtiramiz
birlik uzunligi, ya'ni har bir chegara funktsiyasi uchun biz ko'rib chiqamiz
faqat birlik radiusli sferada yotgan uning amalga oshirilishi
+ men? + • • • + an • Har bir funktsiya uchun / biz uning qismini topamiz
shar nuqtasi A (f) = (a ^, a {, ..., # £) gacha bo'lgan eng katta masofa
eng yaqin giperplane. Bunga A dan AB perpendikulyarini tushiramiz
giperplan, \ AB \ = r (/). Giper tekisliklarning normalari (8) shaklga ega
(1, ± 1, ± 1, ..., zb 1) / Y72 + 1 va A dan eng yaqingacha bo'lgan r masofasi uchun
giperplan, r n ^ °°
Demak, agar C OB nurning birlik shar bilan kesishish nuqtasi bo'lsa, u holda
yoyi AC n- + da AB bilan asimptotik tarzda birlashadi
Oddiy pol funktsiyasi uchun / unga mos keladigan hajm
birlik sharining bo'lagi asimptotik ravishda oshmaydi
Guruch. sakkiz
S ^ (R) 2 ^ n +!> / 2 Rn 2-chi (n + 1> / 2 1
Bu hajm asimptotik ravishda r o'lchamli radiusli sharning hajmidan kam emas
Shuning uchun
VUr) =
G
yy ^ / 2
(m + 1
NS
R ^
2l (n + 1) / 2 1
± J \

36-bet

MATQIY FUNKSIYALARNING EOS FUNKSIYALARI VA BOSHQA FUNKSIYALARI 39.
Demak, log Nn ~ n2 ni hisobga olsak, olamiz
logr <~~ p.
A dan ao o'qiga parallel to'g'ri chiziq chizamiz, ya'ni. yo'nalishda
(± 1, 0, 0), nuqtadagi eng yaqin giperplan bilan kesishmaguncha
D. AB va AD orasidagi burchak kosinusining mutlaq qiymati \) Yn + 1,
\ AD \ = y / yn + 1. Funktsiyaning normallashtirilgan realizatsiyasi (25) / c
og'irlik vektorining minimal moduli olingan A nuqtasi bilan berilgan
1 / \ AP \ koeffitsientli gomoteti, ya'ni vektorni ko'paytirish
Yn + i / r bo'yicha birlik uzunligi (<2o, & 1, ..an) bo'lsa, \ A'D '\ = I.
Shunday qilib, normalangan uchun vazn vektorining minimal moduli
realizatsiyalar / Yn + ijr ga teng. Demak, M (/)> 2n (1-0 (1)). Teorema isbotlangan.
Keling, Mc (n) ning yuqori chegaralariga o'tamiz. Ular
yuqori chegaralar va M (n) uchun. Bu erda ma'lum bo'lgan yagona yondashuv
Muroga va boshqalar [84] tomonidan 30 yil oldin taklif qilingan, dan iborat
chegaraviy yechimlar tamoyilidan foydalanib, uchun Kramer qoidasi
chiziqli tenglamalar sistemasi yechimlari va miqdor uchun Hadamard bahosi
determinantlar.
20-teorema [84]. Mc (n) miqdori uchun smeta
(p-M yuqoriga + 1) / 2
MCI <2 (^ MR-)
Isbot. 2P chiziqli tengsizliklar tizimi (24),
normalangan amalga oshirish (fli, ..., an, T) qanoatlantirishi kerak
chegara funksiyasi f: {0, 1) n (0, 1), ruxsat etilgan asosiy yechimga ega
n +1 tengsizliklar tenglik va darajaga aylanganda
mos chiziqli tizimning n + 1 ga teng:
a aix [n + i) + • •. + d "4" +1) - T = - 1, x <"+ 1) e = G1 (0).
Uni Kramer qoidasiga ko'ra yechib, olamiz
a, = A; / A, i - 1, 2, n,
t-d „, / d. <27>
Determinant A, i - 1, 2, ..., n ning absolyut qiymatini baholaylik.
Buni amalga oshirish uchun uning oxirgi ustunini 1/2 ga ko'paytiring va uni qo'shing
boshqa barcha ustunlarga, i-chidan tashqari, va i-dan ayirish. V
natijada biz butunlay ± 1/2 dan tashkil topgan determinantni olamiz. Qadrlash
Hadamardning so'zlariga ko'ra, biz olamiz
| A, [ij (nl-iU2
(27) barcha a {va T na IAI ni ko'paytirsak, biz butun sonni olamiz
uchun amalga oshirish / unda barcha og'irliklar mutlaq qiymatdan oshmaydi
(n! 1 \ (n + 1) / 2 ^
2 f T-- ~ l? isbotlashga harakat qilinganidek.
Pastki chegaralar (26) va orasidagi katta bo'shliqqa e'tibor bering
Bir tomondan 19-teorema, ikkinchi tomondan 20-teoremadagi yuqori chegara. Oldin
smetasini pasaytirish uchun hozircha ma'lum yondashuv yo'q
20-teorema, hatto butun son talabini tashlasak ham.
Endi (23) dagi p (/) qiymatiga qaytaylik. Agar min | (a, x) - b \ =
u (oh, 1) n
= p, keyin ai = ai / 2pw ni o'rnatib, 7 \ ni mos ravishda tanlab, biz olishimiz mumkin

37-bet

40
Yu. A. Zuev
/ uchun normallashtirilgan realizatsiyani (24) hisoblang. Shuning uchun max ^ M (/), va
_ 1 2pM (f) ^ UW ^ 1n2pM {f).
P (/) = p / W ekan, bundan kelib chiqadi
o'n bir
Demak, 19 va 20 teoremalardan foydalanib, biz hosil qilamiz
l
- n log n ^ log p (n) ~ - log M (n) ^ n.
4. Dizyunktiv normal shaklning murakkabligi. Ostona
funksiya bir hil, shuning uchun uning qisqartirilgan d. n. f. u
yagona o'lik, eng qisqa va minimal. Bo'ladi
faqat shu hisoblangan d. n. f. O'zgartirishlar -> ■ 1 - Xi har qanday chegara
funksiya saqlab turganda monotonga aylantirilishi mumkin
qiyinchiliklar d. n. f., shuning uchun biz monotonlikni hisobga olish bilan cheklanamiz
oddiy implikantlari quyi birliklarga mos keladigan funksiyalar.
Foydalanish chegara funktsiyalarini ifodalashning murakkabligini baholash
d. n. f. ikki sababga ko'ra qiziqish uyg'otadi. Birinchidan,
sezilarli uzunlik d. n. f. chegara funktsiyalari argumentdir
o'rniga mantiqiy funktsiyalarni belgilash uchun ba'zi hollarda foydalaning
d. n. f. chegara ko'rinishlari. Va ikkinchidan, bu tadqiqotlar
NP-' to'liq yechishning algoritmik murakkabligi muammosi bilan shug'ullanish
yigirma yil davomida o'ziga jalb etayotgan vazifalar
matematiklarning diqqat-e'tibori. Haqiqatan ham, yukxalta muammosi (2)
ruxsat etilgan barcha maksimal darajaga qarab hal qilinishi mumkin
echimlar - mos keladigan monoton funktsiyaning yuqori o'q va
bunday skanerlash 0 (n2K) vaqtida amalga oshirilishi mumkin, bu erda K - yuqori soni
nollar [76]. Shunday qilib, agar barcha pol funktsiyalari uchun uzunlik
d. n. f. polinom bilan chegaralangan edi, keyin u darhol ergashdi
Bu P = NP bo'ladi.
Bu chegara funktsiyalari eksponensialga ega bo'lishi mumkin
murakkablik d. n. f., allaqachon ko'pchilik funksiyasining misolini ko'rsatadi, d. n. f.
{[n / 2]) birikmalardan iborat va bu haqiqat, albatta,
muammoning P = NP holatiga hech qanday ta'sir qilmaydi. Chegara olishi mumkin
kattaroq uzunlikka ega bo'lgan funktsiyalar d. n. f.? Yo'q, pastdan beri
monotonik funktsiyaning birliklari tengsiz va maksimal quvvat
Sperner lemmasi bo'yicha juftlik bilan taqqoslanmaydigan to'plamlar to'plamiga teng
([q / 2 ^ * Shunday qilib, quyidagi natija to'g'ri.
Teorema 21. Eshik funksiyasi uchun oddiy implikantlar soni
(NS)
I dan oshmaydi [yy / 2] / •
Ko'pchilik funktsiyasi bo'yicha maksimalga erishilganligi
uzunlik | D. n. f. Murogi tomonidan allaqachon qayd etilgan pol funktsiyalari sinfida
[86]. Savol ostona orasida qanchalik tez-tez, ammo, tug'iladi
funksiyalar, d ning eksponensial uzunligi va. f.? Yechim tajribasi
shunga o'xshash vazifalar bir necha o'n yillik rivojlanish davomida to'plangan
diskret matematika, odatdagi holat bo'lmasligi kerakligini ko'rsatadi
ekstremal va eksponensial murakkablikdan sezilarli darajada farq qiladi
d. n. f. deyarli barcha chegara funktsiyalariga ega bo'lishi kerak. Uchun
Buning isboti PTenpoia ning kuchli usulidan foydalanishni taklif qiladi.
Biroq, uning "peshonasida" qo'llanilishi istalgan natijani bermaydi.
Oʻzgaruvchilarni inkor etmaydigan 2n ta elementar bogʻlanish mavjud,

38-bet

MATQIY FUNKSIYALARNING EOS FUNKSIYALARI VA BOSHQA FUNKSIYALARI.
va ko‘pi bilan k bog‘lovchisi yordamida ko‘pi bilan olish mumkin
2 (.) z = o '1'
u holda ularning deyarli barchasi uzunligi d.n. d., asimptotik ravishda n dan kam emas.
Ushbu smetani yaxshilash uchun bunday emasligini hisobga olish kerak
qo‘shma gaplarning ixtiyoriy kichik to‘plamlari, faqat ayirboshlashlari
chegara funktsiyasi bo'lib, uni bajarish oson emas.
Agar biroz kuchliroq natijaga erishish mumkin
I bilan muntazam funktsiyalarning Rn (l) soni uchun taxminiy (18) dan foydalaning
pastki birliklar. Har qanday monotonik chegara funktsiyasi bo'lishi mumkin
o'zgaruvchilarni muntazam almashtirish orqali amalga oshiriladi, shuning uchun raqam
eng ko'p pastdan pastgacha bo'lgan monoton chegara funktsiyalari mavjud emas
oshadi
n! 2 R „(l) 1 = 0
1 = 0
Bundan biz deyarli barcha chegara funktsiyalari DN uzunligiga ega ekanligini bilib olamiz. f.
asimptotik tarzda n n2 / log n dan kichik [14].
Muallif kuchliroq pastki chegaralarni olish usulini bilmaydi
murakkablik uchun d. n. f. odatiy chegara funktsiyasi, lekin [13] da
Lipkin bilan birgalikda keng sinfning mavjudligi
ko'rsatkichli murakkablikdagi chegara funktsiyalari d. n. f.
Dn (l) n ning monoton chegara funksiyalari soni bo'lsin
I kichik birliklarga ega o'zgaruvchilar. Keyin, Spernerning lemmasidan kelib chiqqan holda,
Dn ([rc / 2]) "juft n uchun 1, toq n va Z uchun Dn ([n / 2]) ^ 2) n (Zj = Q
I> uchun ([n / 2])
22-teorema [13]. 1 (n) = 2 cn (1 + 0 (1)), 0 monoton chegara funktsiyalarining Dn (I) soni uchun I pastroq
birlik bo'lsa, quyidagi asimptotik taxmin haqiqiydir
logDn (l)> c (1-c) n2 / 2.
Isbot chegara o'zgarishi usulidan foydalanadi va in
kontseptual jihatdan raqam uchun pastki chegaralar isbotiga yaqin
berilgan kardinallikning chegara to'plamlari. U quyidagilarga asoslanadi
hisobga olish. Monotonlikni belgilovchi tengsizlik (1) bo'lsin
I pastki birliklar bilan pol funktsiyasi, asta-sekin b pol
giperplane parallel ravishda harakatlanishi uchun ortadi. Ni nazarida
10-teoremaga ko'ra, giperplanet ketma-ket bo'ylab kesishadi deb taxmin qilishimiz mumkin
kubning barcha uchlari. Har bir cho'qqi kesib o'tgan, bo'lish
undan oldingi vaqtda pastki birlik
gipertekislik bilan kesishish, ayni paytda nol cho'qqiga aylanadi
chorraha. Keyingi cho'qqini kesib o'tishda pastki birliklar soni
birlik bilan cho'qqilari bo'lganligi sababli ortishi mumkin
funksiyaning kesishgan qiymatdan kattaroq qiymatlari pastroq bo'ladi.
U faqat bittaga kamayishi mumkin. Etarlicha
chegaraning katta qiymati, funktsiya bir xil va ga teng bo'ladi
Shuning uchun har qanday Zi, CKZi ^ Z butun soni uchun pastki birliklar bo'lmaydi,
ft chegarasining shunday qiymati mavjudki, a \ X \ + ... + anxn < tengsizlik.
B \ 1 \ pastki bo'lgan funktsiyani belgilaydi.
Bu izoh har qanday n uchun Z>3 degan xulosaga kelishimizga imkon beradi
munosabat haqiqatdir
1
Dn (T)> 2 # «- 2 (k).
^ -H / 2]
(28)

39-bet

42
Yu. A. Zuev
Darhaqiqat, har bir l \ uchun [1/2] ^ fa ^ fa ta'rifi bo'yicha
n - 2 o'zgaruvchida Dn - 2 (fa) monoton chegara funktsiyalari mavjud
P— 2
fa pastroqlari bilan. Agar 2 a% x \ r = 1
n-2
2 a% x% ^ ^ 2 funktsiyasi fa - bo'lishi uchun 62 ni tanlaymiz.
r = 1
= Z - Zi - 1 pastki birlik, biz bilan n o'zgaruvchining funktsiyasini quramiz
tengsizlik
yy-2
Xn + (b - b!); Rn-i + (6 - b2) xn i = l
bu erda b = 00 (etarlicha katta). Funktsiya (29) Zi pastki birliklariga ega
pastki kubda xn_i = 1, a £ n - 0 va fa pastki kubda xn - \ = 0 pastki birliklardir,
xn = 1, shuningdek pastki (0, ..., 0, 1, 1), jami l \ + fa + 1 = 1
pastki birliklar. (28) dan foydalanib, buni olish oson
k ^ (n-3) / 2
Dn (l)> 2 Dn-rk-r (h) - (30)
l ^ UI 2]
(30) k = [{n ~ log Z) / 2 - log n] ning o'rniga qo'yiladi va bu holda hisobga olinadi.
/ n - 2k - 2 \
\ [n / 2] k - l)> ^ va shuning uchun Dn-2k-2 (l) ^ 1, biz tasdiqni olamiz
teorema.