Arifmetik sxemaning murakkabligi - Arithmetic circuit complexity

Yilda hisoblash murakkabligi nazariyasi, arifmetik davrlar hisoblash uchun standart modeldir polinomlar. Norasmiy ravishda, arifmetik sxema o'zgarmaydigan yoki raqamlarni kiritishda qabul qiladi va u allaqachon hisoblab chiqqan ikkita ifodani qo'shishga yoki ko'paytirishga ruxsat beriladi. Arifmetik sxemalar hisoblash polinomlarini murakkabligini tushunishning rasmiy usulini beradi. Ushbu tadqiqot yo'nalishidagi savollarning asosiy turi "berilgan polinomni hisoblashning eng samarali usuli qanday?" ${displaystyle f}$ ?"

Ta'riflar

Oddiy arifmetik sxema.

An arifmetik sxema ${displaystyle C}$ ustidan maydon ${displaystyle F}$ va o'zgaruvchilar to'plami ${displaystyle x_ {1}, ldots, x_ {n}}$ a yo'naltirilgan asiklik grafik quyidagicha. Undagi har bir tugun daraja nol an deyiladi kirish eshigi va o'zgaruvchan tomonidan belgilanadi ${displaystyle x_ {i}}$ yoki maydon elementi ${displaystyle F.}$ Har qanday boshqa darvoza ikkalasi tomonidan belgilanadi ${displaystyle +}$ yoki ${displaystyle imes;}$ birinchi holda bu a sum darvoza va ikkinchisida a mahsulot Darvoza. An arifmetik formula bu har bir darvoza ega bo'lgan sxema ustunlik bittasi (va shuning uchun asosiy grafik a yo'naltirilgan daraxt ).

O'chirish sxemasi u bilan bog'liq ikkita murakkablik o'lchoviga ega: o'lcham va chuqurlik. The hajmi zanjir - bu undagi eshiklar soni va chuqurlik zanjir - undagi eng uzun yo'naltirilgan yo'lning uzunligi. Masalan, rasmdagi sxema oltita kattalikka va chuqurlik ikkiga ega.

Arifmetik sxema polinomni quyidagi tabiiy usulda hisoblab chiqadi. Kirish eshigi u belgilagan polinomni hisoblab chiqadi. Sum darvozasi ${displaystyle v}$ uning farzandlari tomonidan hisoblangan polinomlarning yig'indisini hisoblaydi (darvoza) ${displaystyle u}$ a bola ning ${displaystyle v}$ agar yo'naltirilgan chekka bo'lsa ${displaystyle (v, u)}$ (grafada) Mahsulot darvozasi o'z farzandlari tomonidan hisoblangan polinomlar mahsulotini hisoblab chiqadi. Rasmdagi sxemani ko'rib chiqing, masalan: kirish eshiklari hisoblash (chapdan o'ngga) ${displaystyle x_ {1}, x_ {2}}$ va ${displaystyle 1,}$ sum eshiklari hisoblab chiqiladi ${displaystyle x_ {1} + x_ {2}}$ va ${displaystyle x_ {2} +1,}$ va mahsulot eshigi hisoblab chiqadi ${displaystyle (x_ {1} + x_ {2}) x_ {2} (x_ {2} +1).}$

Umumiy nuqtai

Polinom berilgan ${displaystyle f,}$ biz uni hisoblashning eng yaxshi usuli qanday deb so'rashimiz mumkin - masalan, elektron hisoblashning eng kichik hajmi qanday ${displaystyle f.}$ Bu savolga javob ikki qismdan iborat. Birinchi qism topishdir biroz hisoblash davri ${displaystyle f;}$ odatda bu qism deyiladi yuqori chegara ning murakkabligi ${displaystyle f.}$ Ikkinchi qism buni ko'rsatmoqda yo'q boshqa sxema yaxshiroq ishlashi mumkin; bu qism deyiladi pastki chegara ning murakkabligi ${displaystyle f.}$ Ushbu ikkita vazifa bir-biriga chambarchas bog'liq bo'lsa-da, pastki chegaralarni isbotlash odatda qiyinroq bo'ladi, chunki pastki chegarani isbotlash uchun bahslashish kerak barchasi bir vaqtning o'zida sxemalar.

E'tibor bering, bizni polinomlar aniqlaydigan funktsiyalar emas, balki polinomlarni rasmiy hisoblash qiziqtiradi. Masalan, polinomni ko'rib chiqing ${displaystyle x ^ {2} + x;}$ ikki element maydonida bu polinom nol funktsiyani ifodalaydi, ammo shunday emas nol polinom. Bu arifmetik davrlarni o'rganish bilan o'rganish o'rtasidagi farqlardan biridir Mantiqiy davrlar. Mantiqiy murakkablikda, asosan, funktsiyani hisoblash ba'zi bir vakolatlarni emas, balki ularni hisoblashda manfaatdor (bizning holimizda, polinom bilan tasvirlash). Bu mantiqiy murakkablikni arifmetik murakkablikdan ko'ra qiyinlashtiradigan sabablardan biridir. Arifmetik davrlarni o'rganish, shuningdek, mantiqiy ishni o'rganish uchun oraliq bosqichlardan biri sifatida qaralishi mumkin,^[1] biz buni deyarli anglamaymiz.

Yuqori chegaralar

Hisoblash polinomlarini murakkabligini o'rganish doirasida ba'zi bir aqlli sxemalar (alternativa algoritmlar) topildi. Taniqli misol Strassenniki uchun algoritm matritsa mahsuloti. Ikkala mahsulotni hisoblashning to'g'ri usuli ${displaystyle n imes n}$ matritsalar o'lchamlari tartibini talab qiladi ${displaystyle n ^ {3}.}$ Strassen biz aslida ikkita matritsani kattalashtirish sxemasidan foydalanib ko'paytira olishimizni ko'rsatdi ${displaystyle n ^ {2.807}.}$ Strassenning asosiy g'oyasi - bu ikkitadan matritsaga ko'paytirishning aqlli usuli. Ushbu g'oya taxminan vaqtni talab qiladigan ikkita matritsani ko'paytirishning eng yaxshi nazariy usulining boshlang'ich nuqtasidir ${displaystyle n ^ {2.376}.}$

Hisoblashning yana bir qiziqarli hikoyasi yotadi aniqlovchi ning ${displaystyle n imes n}$ matritsa. Determinantni hisoblashning sodda usuli taxminan o'lchamdagi sxemalarni talab qiladi ${displaystyle n !.}$ Shunga qaramay, biz o'lchamdagi polinomning sxemalari mavjudligini bilamiz ${displaystyle n}$ determinantni hisoblash uchun. Biroq, bu sxemalar chiziqli chuqurlikka ega ${displaystyle n.}$ Berkovits takomillashtirishni taklif qildi: o'lchamdagi polinomlar sxemasi ${displaystyle n,}$ lekin chuqurlikda ${displaystyle O (log ^ {2} (n)).}$ ^[2]

Biz uchun ma'lum bo'lgan eng yaxshi sxemani ham eslatib o'tmoqchimiz doimiy ning ${displaystyle n imes n}$ matritsa. Determinantga kelsak, doimiy uchun sodda elektron taxminan o'lchamga ega ${displaystyle n !.}$ Biroq, doimiy uchun ma'lum bo'lgan eng yaxshi elektron taxminan o'lchamga ega ${displaystyle 2 ^ {n},}$ Rayser formulasi bilan berilgan: uchun ${displaystyle n imes n}$ matritsa ${displaystyle X = (x_ {i, j}),}$

{displaystyle operator nomi {perm} (X) = (- 1) ^ {n} sum _ {Ssubseteq {1, ldots, n}} (- 1) ^ {| S |} prod _ {i = 1} ^ {n } sum _ {jin S} x_ {i, j}}

(bu chuqurlik uch zanjir).

Pastki chegaralar

Pastki chegaralarni isbotlash nuqtai nazaridan bizning bilimimiz juda cheklangan. Rasmiy polinomlarni hisoblashni o'rganganimiz uchun juda katta darajadagi polinomlar katta davrlarni talab qilishini, masalan, daraja polinomini bilamiz. ${displaystyle 2 ^ {2 ^ {n}}}$ taxminan o'lchamdagi sxemani talab qiladi ${displaystyle 2 ^ {n}.}$ Shunday qilib, asosiy maqsad kichik darajadagi polinomlar, masalan, in polinomlar uchun pastki chegarani isbotlashdir ${displaystyle n.}$ Darhaqiqat, matematikaning ko'plab sohalarida bo'lgani kabi, hisoblash argumentlari ham bizga juda ko'p polinomial kattalikdagi davrlarni talab qiladigan polinom darajadagi polinomlar mavjudligini aytadi. Ammo, bu hisoblash argumentlari odatda bizning hisoblash haqidagi tushunchamizni yaxshilamaydi. Quyidagi muammo ushbu tadqiqot sohasidagi asosiy ochiq muammo hisoblanadi: toping aniq super polinomial kattalikdagi davrlarni talab qiladigan polinom daraja polinomi.

San'atning holati a ${displaystyle Omega (nlog d)}$ elektron hisoblash hajmi uchun pastki chegara, masalan, polinom ${displaystyle x_ {1} ^ {d} + cdots + x_ {n} ^ {d}}$ tomonidan berilgan Strassen va Baur va Strassen tomonidan. Aniqroq aytganda, Strassen Bezout lemmasidan foydalanib, bir vaqtning o'zida hisoblaydigan har qanday elektronni ko'rsatdi ${displaystyle n}$ polinomlar ${displaystyle x_ {1} ^ {d}, ldots, x_ {n} ^ {d}}$ hajmi ${displaystyle Omega (nlog d),}$ keyinchalik Baur va Strassen quyidagilarni ko'rsatdilar: kattalikdagi arifmetik sxema berilgan ${displaystyle s}$ polinomni hisoblash ${displaystyle f,}$ eng katta hajmdagi yangi sxemani qurish mumkin ${displaystyle O (lar)}$ bu hisoblaydi ${displaystyle f}$ va hamma ${displaystyle n}$ qisman hosilalar ning ${displaystyle f.}$ Ning qisman hosilalari beri ${displaystyle x_ {1} ^ {d} + cdots + x_ {n} ^ {d}}$ bor ${displaystyle dx_ {1} ^ {d-1}, ldots, dx_ {n} ^ {d-1},}$ Strassenning pastki chegarasi qo'llaniladi ${displaystyle x_ {1} ^ {d} + cdots + x_ {n} ^ {d}}$ shuningdek. Bu ba'zi bir yuqori chegaralar pastki chegaralarni isbotlashda yordam beradigan misollardan biridir; Baur va Strassen tomonidan berilgan sxema qurilishi ko'proq umumiy polinomlar uchun pastki chegarani nazarda tutadi.

Pastki chegaralarni isbotlash qobiliyatining etishmasligi bizni hisoblashning oddiy modellarini ko'rib chiqishga undaydi. Ba'zi bir misollar: monotonli zanjirlar (unda barcha maydon elementlari manfiy bo'lmagan haqiqiy sonlar), doimiy chuqurlik davrlari va ko'p chiziqli zanjirlar (har bir darvoza hisoblashda ko'p qatorli polinom ). Ushbu cheklangan modellar keng o'rganilib, ba'zi tushunchalar va natijalarga erishildi.

Algebraik P va NP

Hisoblash murakkabligi nazariyasidagi eng qiziqarli ochiq muammo bu P va NP muammo. Taxminan ushbu muammo, berilgan muammoni echish osonligini aniqlashga qaratilgan bo'lib, berilgan muammoning echimi borligini ko'rsatish mumkin. Valiant o'zining asosiy ishida^[3] ushbu muammoning algebraik analogini taklif qildi VP va VNP muammo.

VP klassi P ning algebraik analogidir; bu polinomlar sinfi ${displaystyle f}$ polinom kattaligi zanjirlari sobit maydonda bo'lgan polinom darajasining ${displaystyle K.}$ VNP klassi NP analogidir. VNP ni polinomlar sinfi deb hisoblash mumkin ${displaystyle f}$ monomiya berilganligi sababli uning koeffitsientini aniqlashimiz mumkin bo'lgan polinom darajasining ${displaystyle f}$ samarali, polinom kattaligi sxemasi bilan.

Murakkablik nazariyasidagi asosiy tushunchalardan biri bu to'liqlik. Ko'p polinomlar sinfi berilgan (masalan, VP yoki VNP), to'liq polinom ${displaystyle f}$ bu sinf uchun ikkita xususiyatga ega bo'lgan polinom: (1) u sinfning bir qismi va (2) boshqa har qanday polinom ${displaystyle g}$ sinfda osonroq ${displaystyle f,}$ agar shunday bo'lsa degan ma'noda ${displaystyle f}$ u holda kichik elektron mavjud ${displaystyle g.}$ Valiant doimiy VNP klassi uchun to'liq ekanligini ko'rsatdi. Shunday qilib, VP ning VNP ga teng emasligini ko'rsatish uchun doimiyning polinom kattaligi davrlari mavjud emasligini ko'rsatish kerak. Bu hal qilinmagan ochiq muammo bo'lib qolmoqda.

Chuqurlikni kamaytirish

Polinomlarni hisoblash bo'yicha tushunchalarimizdan biri Valiant, Skyum, Berkovits va Rakoffning ishidir.^[4] Agar ular polinom bo'lsa, buni ko'rsatdilar ${displaystyle f}$ daraja ${displaystyle r}$ o'lchov sxemasiga ega ${displaystyle s,}$ keyin ${displaystyle f}$ shuningdek, o'lchamdagi polinom zanjiriga ega ${displaystyle r}$ va ${displaystyle s}$ chuqurlik ${displaystyle O (log (r) log (s)).}$ Masalan, darajadagi har qanday polinom ${displaystyle n}$ polinom kattaligi sxemasiga ega, shuningdek chuqurlik polinom kattaligi sxemasiga ega ${displaystyle log ^ {2} (n).}$ Ushbu natija Berkovits davrini polinom kattaligi sxemasiga (masalan, determinant) ega bo'lgan har qanday polinom darajadagi polinomga umumlashtiradi. Mantiqiy sozlamadagi ushbu natijaning analogi yolg'on deb hisoblanadi.

Ushbu natijaning bitta xulosasi - bu kvazipolinomial kattalikdagi formulalar nisbatan kichik formulalar bilan sxemalarni simulyatsiya qilishdir: agar polinom ${displaystyle f}$ daraja ${displaystyle r}$ o'lchov sxemasiga ega ${displaystyle s,}$ unda o'lchamning formulasi mavjud ${displaystyle s ^ {O (log (r))}.}$ Ushbu simulyatsiya Valiant al al. va ilgari Hyafil tomonidan namoyish etilgan.^[5]

Qo'shimcha o'qish

Bürgisser, Piter (2000). Algebraik murakkablik nazariyasining to'liqligi va qisqarishi. Matematikada algoritmlar va hisoblash. 7. Berlin: Springer-Verlag. ISBN 978-3-540-66752-0. Zbl 0948.68082.
Bürgisser, Piter; Klauzen, Maykl; Shokrollaxi, M. Amin (1997). Algebraik murakkablik nazariyasi. Grundlehren der Mathematischen Wissenschaften. 315. Tomas Lickteig bilan hamkorlikda. Berlin: Springer-Verlag. ISBN 978-3-540-60582-9. Zbl 1087.68568.
von zur Gaten, Yoaxim (1988). "Algebraik murakkablik nazariyasi". Kompyuter fanlari yillik sharhi. 3: 317–347. doi:10.1146 / annurev.cs.03.060188.001533.

Izohlar

^ L. G. Valiant. Mantiqiy murakkablik nazariyasi nima uchun qiyin? Mantiqiy funktsiyalarning murakkabligi bo'yicha London Matematik Jamiyati simpoziumi materiallari, 84-94 betlar, 1992 y.
^ S. J. Berkovits. Determinantni oz miqdordagi protsessorlardan foydalangan holda kichik vaqt ichida hisoblash to'g'risida. Inf. Mahsulot 18-xatlar, 147-150-betlar, 1984 y.
^ L. G. Valiant. Algebra bo'yicha to'liqlik darslari. Proc-da. 11-ACM STOC, 249–261 bet, 1979 yil.
^ L. G. Valiant, S. Skayum, S. Berkovits, C. Rakoff. Bir nechta protsessorlardan foydalangan holda polinomlarni tezkor parallel hisoblash. SIAM J. Comput. 12 (4), 641-664 betlar, 1983 y.
^ L. Hyafil. Ko'p o'zgaruvchan polinomlarni parallel baholash to'g'risida. SIAM J. Comput. 8 (2), 120-123 betlar, 1979 y.

[1] L. G. Valiant. Mantiqiy murakkablik nazariyasi nima uchun qiyin? Mantiqiy funktsiyalarning murakkabligi bo'yicha London Matematik Jamiyati simpoziumi materiallari, 84-94 betlar, 1992 y.

[2] S. J. Berkovits. Determinantni oz miqdordagi protsessorlardan foydalangan holda kichik vaqt ichida hisoblash to'g'risida. Inf. Mahsulot 18-xatlar, 147-150-betlar, 1984 y.

[3] L. G. Valiant. Algebra bo'yicha to'liqlik darslari. Proc-da. 11-ACM STOC, 249–261 bet, 1979 yil.

[4] L. G. Valiant, S. Skayum, S. Berkovits, C. Rakoff. Bir nechta protsessorlardan foydalangan holda polinomlarni tezkor parallel hisoblash. SIAM J. Comput. 12 (4), 641-664 betlar, 1983 y.

[5] L. Hyafil. Ko'p o'zgaruvchan polinomlarni parallel baholash to'g'risida. SIAM J. Comput. 8 (2), 120-123 betlar, 1979 y.

[1]

[2]

[3]

[4]

[5]