Je hipoteza eksponentnega časa napačna? Predavanje o nedokončani trditvi

Vir, odlomek za odlomkom

Prepis, preveden z umetno inteligenco iz angleščine.

1. u1 0:02 No, pa poskusimo. Em, prav, torej prekinjamo naš redni pouk teorije zahtevnosti, da bi poskusili dokazati, da ETH ne velja in da je SAT mogoče rešiti v podeksponentnem času. To je izšlo pred nekaj dnevi.

   

2. u2 0:18 Torej to predavanje ne bo zelo dobro pripravljeno. Običajno rad vse popolno zvadim in imam pripravljene popolne zapiske ter poznam vse podrobnosti. Tu spredaj sem ves uglajen, upam, danes pa bo ravno nasprotno. Nisem veliko spal. Pravzaprav ne vem, kako bo šlo.
3. u3 0:35 Ne razumem vseh delov dokaza. Ampak dobil sem dobro zamisel: to je moja trenutna, saj veste, različica pisnega dokaza, pripravljena z UI. Zato prosim vsi vzemite prenosnike. Odprite to, dajte svojemu agentu in potem, če se mi zatakne, preprosto recite: profesorju se je zataknilo pri dokazovanju tega dela, in mi pomagajte, prav?
4. u4 0:57 Prav, pa poskusimo.
5. u5 0:58 >> [smeh]
6. u6 0:59 >> Em, bomo videli, kako daleč pridemo ali kaj se zgodi. Nimam načrta. Prav, torej poskusili bomo dokazati, da je SAT v podeksponentnem času, kar je precej imenitno. To je precej boljše. Mislim, to je manjše od 1.000.01 pri poljubnem številu ničel.
7. u7 1:17 Torej je res podeksponentno. Kaj še želim povedati? Aha, pravzaprav je precej boljše od tega. Oprostite, tu bi moralo pisati 3-SAT. Precej boljše je od tega. Ne bo šlo samo za to, da vam dam formulo 3-SAT v obliki 3-CNF, vi pa poveste, ali ima izpolnjujočo prireditev ali ne.
8. u8 1:37 Natančno bomo prešteli izpolnjujoče prireditve. Dokazali bomo torej precej močnejši rezultat, da je tudi število rešitev 3-SAT, #3-SAT, mogoče izračunati v tem eks- podeksponentnem času. Prav, zato je odlično, da smo imeli prejšnjič predavanje o zahtevnosti štetja. Em, prav.
9. u9 1:57 Torej to je rezultat. Aha, kot je tudi opozoril Bernardo, ki je tukaj, če ste pametni in naredite nekaj bolj prefinjenega od običajnega Cook-Levina, to pomeni tudi, da je vse, kar je rešljivo v nedeterminističnem času n, mogoče rešiti tudi v tem času.
10. u10 2:21 To je torej res odlično. Prav, dokazal vam bom to ob nekakšni blagi predpostavki. Dokazal bom ob predpostavki, da ima dana formula 3-SAT število klavzul reda n.
11. u11 2:40 Prav, ima n spremenljivk in lahko ima, mislim, do n na tretjo klavzul, vendar bomo predpostavili, da je redka, da ima število klavzul reda n. In želim povedati, da to ni kakšna huda predpostavka. Prejšnja dela na področju finozrnate zahtevnosti bi pokazala, da lahko, če to dokažete ob predpostavki števila klavzul reda n, dokažete tudi na splošno, le da bi morda izgubili ta kvadratni koren in bi postal log n na potenco recimo 1 skozi 30 ali kaj podobnega, kar bi bilo še vedno izjemno.
12. u12 3:13 Pravzaprav ima dokaz OpenAI poleg redčenja še nekaj dodatnih trikov, ki z nečim pametnejšim pokažejo natanko ta rezultat s kvadratnim korenom n tukaj. Tega dela nisem preučil, zato ne vem, kako gre, ampak dolg je samo kakšne tri ali štiri strani.
13. u13 3:33 Kakor koli, dokazal vam bom to različico in bomo zadovoljni. Ja, in če naredim kakšno napako, mi povejte, če jo opazite. Prav, če bi imeli naše običajno 18. predavanje, bi govorili o #P in permanentu ter o tem, da je permanent #P-poln, in videli bi tisto tri-klasično, ampak ta problem, #3-SAT, ali pravzaprav kateri koli problem štetja za, saj veste, CSP, se reducira na permanent, na katerega vas bom spomnil, na računanje permanenta.
14. u14 4:12 In redukcija ohranja število izpolnjujočih prireditev oziroma odgovor do fiksnega znanega faktorja ter ohranja velikost in podobno. Zato zadošča pokazati, da je tudi permanent redkih matrik n krat n s številom neničelnih elementov reda n mogoče izračunati v istem času.
15. u15 4:43 Prav, to je v bistvu klasična redukcija, ki jo je podal Valiant, drugi pa so jo poenostavili. Naj vas malo spomnim, kaj je permanent. Permanent je tudi, prav, prav, permanent, če imate matriko A, ste ga že videli, pravzaprav večkrat pri tem predmetu, ampak je nekakšna formula, podobna determinanti.
16. u16 5:05 In če matrika A vsebuje samo ničle in enice, ima zelo naravno številsko interpretacijo. Če vsebuje samo ničle in enice, si jo lahko predstavljate kot matriko bisosednosti dvodelnega grafa z n vozlišči na levi in na desni ter s povezavami glede na to, kje so tukaj ničle in enice.
17. u17 5:28 In permanent matrike šteje popolna prirejanja v tem grafu. Prav, torej ima tudi značaj štetja nekih objektov, ki jih je a priori eksponentno mnogo. In pravzaprav, če ima matrika A še druge elemente, denimo trojko ali recimo, em, si jo lahko predstavljate kot matriko sosednosti grafa z uteženimi povezavami, kjer imajo nekatere povezave utež tri ali morda dve.
18. u18 6:01 Potem je utež popolnega prirejanja produkt uteži njegovih povezav. In če so to pozitivna cela števila, si lahko to pravzaprav predstavljate tudi kot tri vzporedne povezave in tako naprej. Prav tako je v redu, če so elementi negativni. Povezave imajo lahko negativne uteži.
19. u19 6:18 Pravzaprav elegantna različica te redukcije morda naredi matriko z elementi, ne vem, minus ena, nič, ena in morda dve in tri ali kaj podobnega. Torej zelo majhna cela števila. Em, prav.
20. u20 6:37 Formula za permanent je tole. Vsota, in morda vidite, zakaj na splošno šteje popolna prirejanja. Vsota po vseh permutacijah sigma, ki slikajo N v N. To je tudi nekakšna posplošena diagonala v matriki.
21. u21 6:57 Produkt za I od 1 do N, A I sigma I. Prav, vidite, da je enako kot determinanta, le da tukaj ni tistega neumnega faktorja minus ena s predznakom permutacije.
22. u22 7:12 >> [prhne]
23. u23 7:13 >> Em, prav. Kot glavni cilj bomo pokazali ta rezultat: če računate permanent redkih matrik N krat N, lahko to storite v nekoliko podeksponentnem času. O tem bom čez trenutek povedal še nekaj, ampak ravnokar mi je prišlo na misel, da bi moral povedati tudi, ne vem.
24. u24 7:38 Med tem predavanjem se vam bo morda zdelo malo čudno, kot da smo odleteli v vesolje. Začel sem s tem: »Pokazal vam bom, kako rešiti 3-SAT nekoliko učinkoviteje.« In vi si mislite: »Ja, imeli bomo klavzule, izpolnjujoče prireditve, resnično in neresnično in tako naprej.« Zelo kmalu pa bomo imeli matrike, permanente, range matrik.
25. u25 8:00 Imeli bomo polinomsko interpolacijo, nekaj Fourierove analize ali tenzorskega zapisa. In spraševali se boste: »Kaj se dogaja? Mislil sem, da govorimo o SAT.« Ampak pravzaprav se mi zdi lepo, ker mislim, da je vsaka sestavina dokaza teoretikom zahtevnosti precej domača.
26. u26 8:20 Če ste opravili polovico podiplomskega predmeta iz zahtevnosti, kot ste jo vi, ali celo cel predmet, kot ga boste kmalu, res mislim, da boste pri vsakem delu rekli: aha, to so nekako standardne stvari, kakršne učijo pri podiplomski zahtevnosti. In lepo je, da celoten rezultat nastane preprosto tako, da te zamisli združimo na nekoliko domiseln način.
27. u27 8:43 Kakor koli, to je samo za takrat, ko bomo kakšnih 57 minut po začetku poskušali razumeti neko čudno polinomsko interpolacijo bločno diagonalnih matrik. Ne vem. Vnaprej sem vas opozoril, da bomo prišli do tega in da se nam ne bo ravno zdelo, da govorimo o SAT. Ja.
28. u28 8:58 >> Torej mislim, da ima permanent to lastnost naključne samoreducibilnosti. Je to kakor koli koristno pri prehodu s 3-SAT na permanent
29. u29 9:06 >> Ja, torej zelo bomo uporabljali dejstvo, da je permanent podan, mislim, ta lastnost samoreducibilnosti oziroma možnost izračuna permanenta ene matrike z interpolacijo permanentov drugih matrik bo v dokazu izjemno pomembna.
30. u30 9:22 In vse to izhaja iz dejstva, da ta formula kaže, da je permanent polinom stopnje n v elementih matrike. Zato bomo polinome precej uporabljali.
31. u31 9:35 >> Ne vem, ja, torej glede vaše pripombe me zanima, ali imate občutek, da je v predstavitvi SAT s CNF na primer nekaj, kar je manj primerno za dokaz, mislim, da bi ostali v nekakšnem izvornem prostoru.
32. u32 9:50 >> Ja, ne vem. Mislim, pravi teoretik algebraične zahtevnosti bi vam rekel: polinomi so tako krasni, algebra je tako krasna, vse je toliko lepše, ko,
33. u33 10:00 >> [se odkašlja]
34. u34 10:00 >> ne vem, preučujete zahtevnost računanja polinoma namesto neke čudne kombinatorične funkcije. Ja, ne vem. Ko sem poskušal razumeti ta dokaz, ko sem GPT pripravil do tega, da je začel, mislim, nekako sem mu rekel, poskusiva pogledati z vidika permanenta.
35. u35 10:24 Zdelo se mi je precej lepše. Mislim, da entropijski dokaz res poskuša ostati v svetu kombinatorike, in z njim nisem toliko napredoval. Em, prav. Ja.
36. u36 10:40 >> Čakajte, ali je torej ta 3-SAT s številom klavzul reda n enako težak kot 3-SAT?
37. u37 10:45 >> Ne čisto, ampak s klasičnimi tehnikami redčenja je znano, kako reducirati, upam, da bom prav povedal, morda Bernardo ve, kako precej učinkovito reducirati splošni 3-SAT na 3-SAT s številom klavzul reda n.
38. u38 11:03 Dovolj učinkovito, da bi lahko z malo pazljivosti iz tega rezultata za število klavzul reda n dokazali isti rezultat s slabšo potenco pri log n tukaj. Dokaz OpenAI pa opravi še nekaj prilagojenega dodatnega dela, verjetno uporabi dejanski potek dokaza, da ne izgubi niti pri tem eksponentu.
39. u39 11:28 Ampak na primer zagotovo smo vedeli, vsak strokovnjak je vedel in v literaturi je znano, da bi s tem dokazom ovrgli ETH.
40. u40 11:40 >> Morda velja povedati, da ne primerjamo enega primerka z n klavzulami in enega gostega primerka, ampak lahko en gost primerek pretvorimo v podeksponentno število redkih primerkov.
41. u41 11:55 >> Ja, odlično opozorilo. In to je seveda pomembno tudi pri vaši ugotovitvi o času n n, da uporabimo močnejšo obliko redukcije. Prejšnjič smo govorili o razlikah med vrstami redukcij. Močnejšo obliko redukcije, kjer uporabimo dejstvo, da ne bomo pretvorili samo v, samo ponavljam Bernarda.
42. u42 12:10 >> [smeh]
43. u43 12:10 >> En primerek redkega 3-SAT, ampak sub x, lahko si privoščimo podeksponentno mnogo primerkov. Malo se je težko navaditi, da imamo toliko časa. Naredili bomo nekaj takega: izvedli bomo ta korak. Čas izvajanja bo povečal za faktor dve na n skozi polilog n, potem pa bomo rekli: to je v redu.
44. u44 12:31 Povečanje časa izvajanja za dve na n skozi log na deseto n je zanemarljivo. To je čuden način razmišljanja, ampak navaditi se ga moramo. Omeniti moram še, če niste veliko razmišljali o računanju permanenta, da se vam morda zdi še bolj impresivno, da lahko permanent izračunamo v času dve na mali o od n, saj je ob pogledu na to formulo videti, da naivni algoritem za permanent potrebuje čas n fakulteta, kar je precej več od dve na n.
45. u45 13:09 To je približno n na n. Zato moramo vsekakor imeti pri roki dobro znano dejstvo iz šestdesetih let, do katerega bi po običajnem vrstnem redu pri tem predmetu prišli čez, ne vem, ne prav veliko predavanj: permanent je tudi brez redkosti izračunljiv v bistvu v času DVE NA N.
46. u46 13:38 >> [aplavz]
47. u47 13:41 >> ČE STE PAMETNI, LAHKO TUKAJ POSTAVITE NEKAJ TAKEGA KOT N NA ENA. To se običajno IMENUJE RYSERJEVA FORMULA.
48. u48 13:48 >> [aplavz]
49. u49 13:50 >> TO JE TISTI ČLOVEK IZ ŠESTDESETIH LET. Mislim, da je to dokazal leta 1967. Vendar lahko to naredite tudi preprosto z dinamičnim programiranjem, kar vam bom poskusil skicirati. Ryserjeva formula je eleganten način, kako to videti, lahko pa tudi malo manj elegantno.
50. u50 14:11 Prav, torej imejte to v mislih kot izhodišče: permanent lahko izračunamo v času dve na n. In poskušamo doseči nekaj malo boljšega. Za to ne potrebujemo redkosti ali česa podobnega. Naj vam na kratko pokažem, zakaj to velja.
51. u51 14:33 Upam, da mi bo uspelo kar sproti. Prav, kako bi permanent izračunali na roke? Kako izračunate determinanto na, to je enako kot determinanta, samo lažje. Kako izračunate determinanto na roke? Naučijo vas različico, pri kateri vzamete ta element, rekurzivno izračunate determinanto tega in pomnožite s tem, potem pa minus ta element krat determinanta, ko prečrtate to, pa plus minus, prečrtate determinanto in tako naprej.
52. u52 15:03 Razvoj po kofaktorjih. Permanent je natanko enak, le da ne vstavljate tistih neumnih minusov. In to je nekako vse, mislim, če minuto razmišljate o tem, je precej očitno, zakaj deluje. Pravzaprav rečete: obravnaval bom vse permutacije, pri katerih se prvi element preslika v ena, in nato rekurzivno izračunal, potem tiste, kjer se prvi element preslika v dve, in v tri in tako naprej.
53. u53 15:23 Prav, to morate narediti in spet je videti, da bo trajalo n fakulteta časa. Ampak poskusili boste naslednje. Morda boste hranili veliko, v bistvu boste uporabili memoizacijo.
54. u54 15:41 Najprej boste izračunali vse permanente velikosti ena krat ena v zadnji vrstici. Potem vse permanente velikosti dve krat dve v zadnjih dveh vrsticah, ne nujno iz zaporednih stolpcev. Izračunali boste, ne vem, permanent teh dveh, te matrike dve krat dve.
55. u55 15:59 Potem vse velikosti tri krat tri v zadnjih treh vrsticah in tako naprej. Dokler niste skoraj končali. Imate vse velikosti n minus ena krat n minus ena v zadnjih n minus ena vrsticah.
56. u56 16:19 Ampak tukaj ste zbrali samo dve na, mislim, bomo videli čez trenutek. Prav. Kako naredite naslednji oziroma zadnji korak? Potrebujete to krat permanent tega, ki ste si ga že shranili, plus to krat permanent tega, ki ste si ga že shranili, in tako naprej.
57. u57 16:42 In koliko stvari shranjujete? Za vsako množico S nekako induktivno računate permanent zadnjih S stolpcev in S vrstic ter S stolpcev.
58. u58 17:03 Torej shranjujete samo dve na S stvari, dve na n stvari, po eno za vsak S. In zato lahko to naredite v bistvu v času dve na n. To bomo potrebovali, potrebovali pa bomo tudi, in morda bom pozneje povedal več, pa bom verjetno pozneje preskočil, da lahko permanent dovolj lepe ali strukturirane matrike, čez trenutek povem, kaj to pomeni, prav tako izračunate precej hitro.
59. u59 17:39 Morda je permanent težko izračunati samo, če imajo elementi neko poljubno strukturo. Prav, naj vam zdaj povem celoten načrt. No, načrt moram še malo spremeniti.
60. u60 17:56 Rekel sem, da bomo permanent redkih matrik izračunali v tem času. Redke pomeni s številom neničelnih elementov reda n. Naj to redkost še malo bolj strukturiram: v vsaki vrstici in stolpcu naj bo število neničelnih elementov reda ena.
61. u61 18:21 Prav, oziroma na tej sliki, če pogledate samo
62. u62 18:24 >> [prhne]
63. u63 18:25 >> kje je podpora, kje so povezave, neničelni elementi, to pomeni graf z omejeno stopnjo na obeh straneh. Morda mislite, da je to še dodatna omejitev, ampak zagotavljam vam, da jo lahko prav tako zelo preprosto vključimo v to redukcijo. Torej zadošča, da znamo narediti to.
64. u64 18:46 Prav, in v nekem smislu, torej poskusil bom zdaj napisati načrt. Celoten načrt je vzeti vhodno matriko, recimo A, ki skoraj nima strukture, in narediti bolj strukturirane različice, tako da je računanje permanenta teh različic učinkovito, torej boljše od časa 2 na n, in da nam računanje permanenta teh bolj strukturiranih različic pomaga izračunati permanent prvotne matrike A.
65. u65 19:18 In to je že malo v tem duhu: z nekaj predhodnimi triki, še preden smo se lotili problema, smo jo naredili malo bolj strukturirano, tako da nima samo števila neničelnih elementov reda n, ampak ima v vsaki vrstici in stolpcu število neničelnih elementov reda ena. Ja.
66. u66 19:33 >> Si lahko predstavljamo, da so vsi elementi ničle in enice, ali je bistveno pomembno, da so lahko negativni?
67. u67 19:39 >> Dobro vprašanje. Pri vsem, kar bom zdaj naredil, se lahko, če vam je ljubše, pretvarjate, da so elementi ničle in enice. Ne bodo, morda lahko dosežemo, da so minus ena, nič in ena, ampak mislim, da ne moremo doseči, da so nič in ena, ne da bi redukcija nehala biti učinkovita.
68. u68 20:00 Ampak za predstavo je pri vsem, kar bomo počeli, čisto v redu, če se pretvarjate, da so samo ničle in enice. Prav. Torej to je načrt celotnega dokaza. In je tudi nekoliko v tistem duhu, ki sem ga prej omenil.
69. u69 20:21 Torej obstaja matrični polinom
70. u70 20:30 >> [aplavz]
71. u71 20:31 >> ali polinomska matrika. Ne vem, kako naj temu rečem. A od T. Poskusil bom z besedami povedati, kaj je to. Lahko si to predstavljate preprosto kot matriko n krat n, katere elementi so polinomi ene spremenljivke T.
72. u72 20:47 To je en način. Tukaj ima na primer 1 + T in T - T na kvadrat, kar koli. Lahko pa si jo predstavljate kot matriko A0 + T * matrika A1 + T na kvadrat * matrika A2 in tako naprej. Morda je ta pogled nekoliko boljši.
73. u73 21:08 Tako se ne napiše polinom. A T z naslednjimi lastnostmi. Najprej, prav, tako da
74. u74 21:25 >> [prhne]
75. u75 21:26 >> stopnja A T
76. u76 21:29 >> [aplavz]
77. u77 21:30 >> znaša v bistvu največ koren iz log n. Če že morate vedeti, je tukaj še log log. In veliki O, ampak kakor koli. Aha, še nekaj bi moral povedati.
78. u78 21:49 Dokaz, ki ga bom pokazal, bo imel tukaj dva log log, medtem ko lahko dokaz OpenAI ob dovolj truda očitno doseže en log log. S tem se vsekakor ne bom ukvarjal. Prav. Stopnja je torej zelo nizka, koren iz log n. To pa zlasti pomeni, da bomo preučevali tudi permanent A T.
79. u79 22:16 In ta ima stopnjo največ n krat koren iz log n. Naj ne pišem faktorjev log log. Ker ima permanent, kot smo že omenili, stopnjo n. Če imajo zdaj vsi elementi stopnjo do korena iz log n, ima celota to stopnjo.
80. u80 22:34 >> [prhne]
81. u81 22:36 >> A0 je A. Matrika, katere permanent poskušate izračunati. In to je morda težko izračunati, vendar bo permanente drugih A I lažje izračunati.
82. u82 23:01 Torej bo to izračunljivo v času dve na n skozi polilog n. In to za I od ena do parametra L.
83. u83 23:22 O tem bom več povedal čez trenutek. Ampak kot sem rekel, predstavljajte si to kot izjemno hitro. To je zanemarljivo hitro v primerjavi s tem, ker bo ta polilog, ne vem, log n na deseto ali pa lahko vzamete poljubno veliko potenco logaritma. Ja?
84. u84 23:37 >> Ko rečete A I, je tam I vstavljen za T ali I vstavljen
85. u85 23:41 >> Ja. I vstavljen za T. Dobesedno si bomo, mislim, ja, morda je malo presenetljivo, ampak dobesedno si bomo predstavljali, da za T vstavljamo cela števila 0, 1, 2, 3, …, L. Prav. In L bo v bistvu log n.
86. u86 24:00 Pravzaprav bo, mislim, deljeno z log log n. Ta je nekoliko pomemben, deljeno z log log n. V bistvu log n. In tega še ne morete videti, ampak naj to poimenujem D.
87. u87 24:21 Stopnja. Ves ta prihranek, kvadratni koren iz log n, bo izviral iz dejstva, da je stopnja D za faktor koren iz log n manjša od L. Tega še ne vidite, čeprav boste kmalu nekoliko videli.
88. u88 24:38 Nisem še niti končal pisanja načrta, ampak v načrtu bi bilo morda to, kar želimo doseči, preprosto, če bi lahko dovolili, da je D enak L, domiselnost celotnega načrta pa bo v tem, da to dosežemo z D, ki je za koren iz log n manjši od L. Prav.
89. u89 24:59 Kot zelo drobno pripombo naj še, o, zmanjkuje mi prostora. No, to je tehnično, zato se s tem ne obremenjujte preveč, ampak permanent je izračunljiv v tem kratkem času.
90. u90 25:19 TUDI ZA VSAKO PODMATRIKO A Z INDEKSOM I. MHM. S tem se ne obremenjujte preveč, bistvo je, da bo A I imel zelo lepo strukturo. Precej strukturiran bo, zato bo lažje izračunati njegov permanent.
91. u91 25:35 In to lepo strukturo bodo imele tudi vse njegove podmatrike, zato bo tudi njihove permanente lahko izračunati. In zdaj zadnji del: permanent A od T je polinom v T.
92. u92 25:55 Zanimali nas bodo njegovi odvodi po T. To je samo polinom ene spremenljivke. Preslika T v število. Zanimali nas bodo njegovi odvodi. In te odvode bomo vrednotili pri, no, pri I od 1 do L.
93. u93 26:13 In tudi te bo mogoče učinkovito izračunati. Torej K-ti odvod tega perm A T pri katerem koli T je enako I, no, katerem koli T in L, mislim.
94. u94 26:37 Je izračunljiv v
95. u95 26:40 >> [se odkašlja]
96. u96 26:46 >> Izračunljiv bo v nekoliko slabšem času od tega. Torej ta čas, grozno razporejam stvari po tabli, ampak ta čas krat neki faktor, ki se slabša, ko K raste.
97. u97 27:04 In ta faktor, ki se slabša, ko K raste, je približno N skozi K na K. Nekaj takega kot N nad K.
98. u98 27:13 >> [zavzdihne]
99. u99 27:14 >> Prav, in ne vem, če za K vstavite ena ali nič. Mislim, to je nekako močnejše od tega, ampak vse te odvode je vse težje izračunati. Bistvo pa je, da je tudi to število nekoliko oddaljeno od polnih dve na N, dokler je K nekoliko oddaljen od N.
100. u100 27:38 Kmalu vam bom pokazal, zakaj smo končali, ko imamo ta načrt. Kakšno vprašanje o dosedanji formulaciji načrta?
101. u101 27:49 >> Kakšen je čas v zadnjem delu?
102. u102 27:52 >> Ja, K-ti odvod je torej izračunljiv v času dve krat dve na N skozi polilog N. In to je, ne vem, log N na deseto, lahko pa vzamete velik polilog N. Torej toliko časa, kot potrebujete za osnovni permanent, krat faktor, ki raste s K, ko poskušate izračunati K-ti odvod, in raste precej hitro, ampak ne grozljivo hitro.
103. u103 28:14 Ja.
104. u104 28:15 >> Torej zdaj delamo interpolacijo.
105. u105 28:17 >> Ja, ja, to je naslednji korak.
106. u106 28:19 >> To je nekako domiseln način zapisa
107. u107 28:20 >> Ja.
108. u108 28:21 >> Število mest, kjer vrednotimo, je precej manjše od faktorja
109. u109 28:24 >> Ja. Natanko to bom zdaj povedal. Prav, morda si mislite, da ne veste, kam merim, ali pa vidite, da smo z interpolacijo skoraj končali. Prav, zdaj bomo uporabili interpolacijo.
110. u110 28:49 Prav, zaradi kratkosti morda zapišimo P od T, hermitski od A od T.
111. u111 28:59 >> [aplavz]
112. u112 29:00 >> In to je čisto običajen polinom ene spremenljivke, kakršne obravnavate v osnovni šoli. P od T. In strašno nas zanima ta vrednost. Vrednost pri nič, tukaj pa je ena, dve.
113. u113 29:20 To gre do L. In stopnja tega je, kot smo rekli, če zanemarimo majhne faktorje, približno N krat koren iz log N. Pri vsej interpolaciji, ki smo jo prej delali pri predmetu, bi običajno rekli: če ima vaš polinom stopnjo D oziroma N log koren iz log N in ga lahko izračunate na toliko plus ena različnih mestih, to zadošča za določitev polinoma.
114. u114 29:48 Določite polinom in ga lahko izračunate na katerem koli drugem mestu, recimo pri nič. In samo po tem delu sodeč ni videti prav dobro, ker je mest, kjer ga lahko učinkovito izračunamo, samo L, kar je približno log N. Lahko izračunamo vse te vrednosti, ampak to je precej manj od determinante oziroma stopnje.
115. u115 30:10 Ampak izračunamo lahko tudi odvode. Na primer poznamo tudi naklon tukaj, naklon tukaj, naklon tukaj, vse te naklone. Poznamo tudi druge in tretje odvode in tako naprej. In vsak odvod nam da nekakšen podatek o polinomu.
116. u116 30:29 To je omejitev glede tega, kakšen je lahko polinom. In za določitev polinoma potrebujete samo strogo več omejitev kot neznank. Če malo pomislite, je vse pravzaprav linearen sistem. P je neznan v tem smislu, da ima neznane koeficiente.
117. u117 30:48 In trditev, da ima v določenih točkah določene vrednosti, je linearna omejitev zanje. Trditev, da imajo odvodi določene vrednosti, je druga linearna omejitev. Po linearni algebri torej potrebujemo več omejitev kot neznank in nekako bomo poznali P. To je nekoliko bolj prefinjena oblika interpolacije, ki jo GPT imenuje Hermitova interpolacija, ampak mislim, da je v teoretičnem računalništvu dobro znano, da lahko interpoliramo tudi z odvodi.
118. u118 31:17 Kaj torej potrebujemo za uspeh? Potrebujemo več podatkov, kot je neznank. Recimo, da uporabimo n s strešico odvodov.
119. u119 31:39 Torej K, oznaka odvoda tukaj, gre do n s strešico. Tako mu pravim, ker bo malo manjši od n s strešico n. Prav, skupno število omejitev bo n s strešico krat L.
120. u120 31:57 Za vsako od teh L točk poznamo n s strešico odvodov ali, ne vem, n minus n s strešico minus ena, kar koli. In potrebujemo, da je to večje od stopnje, ki je n krat d, pri čemer je d ta koren iz log n.
121. u121 32:14 Ja. Torej potrebujemo, mislim, da je n s strešico skozi n vsaj d skozi L. Torej mora biti n s strešico kar precej velik delež n
122. u122 32:31 >> [se odkašlja]
123. u123 32:32 >> da to deluje. Vidite, zato sem rekel, da je pomembno, da je d precej manjši od L. Od tod nekako izvira prihranek. In pri nas je D opazno manjši od L. Zato je to razmerje, če zanemarimo log log, približno ena skozi koren iz log N.
124. u124 32:55 To pomeni, da mora biti N s strešico večji od N skozi koren iz log N. V nekem smislu potrebujemo samo to. Torej je v redu, če je N s strešico, ne vem, do faktorjev log log samo N skozi koren iz log N.
125. u125 33:15 Prav, zbrati moramo samo toliko odvodov. Ja.
126. u126 33:17 >> Oprostite, zakaj je tukaj ravno N krat to?
127. u127 33:21 >> Aha, D je stopnja tega matričnega polinoma. Njegov permanent ima torej stopnjo N krat D. Ker ima permanent stopnjo N. Torej ko vstavite polinom stopnje T v, ja.
128. u128 33:35 >> Torej je to preprosto dejstvo, da lahko, če imate toliko odvodov, sestavite ta sistem enačb in dobite nazaj dejansko enačbo funkcije?
129. u129 33:46 >> [se odkašlja]
130. u130 33:46 >> Ja. Če koeficiente tega neznanega polinoma obravnavate kot neznanke, so vsi ti podatki o odvodih enačbe o teh koeficientih. Ko imate dovolj enačb, lahko izračunate neznanke.
131. u131 34:03 Potem preprosto poznate polinom P. To zlasti pomeni, da lahko vanj vstavite nič in dobite odgovor. Ja.
132. u132 34:10 >> Torej N in L bistveno uporabljata dejstvo [se odkašlja], da pod- [prhne] lastnost odvodov, kajne? Dejstvo, da lahko množimo, namesto da dobimo samo plus L.
133. u133 34:20 >> Oprostite, nisem razumel, kaj?
134. u134 34:23 >> Za vsak odvod, ki ga želimo izračunati, želimo dobiti še L omejitev, kajne?
135. u135 34:29 >> Prav, ja.
136. u136 34:31 >> To bi moralo uporabljati dejstvo, da lahko izračunamo L permanentov z
137. u137 34:38 >> Ja, ja. O tem času bom govoril ravno zdaj.
138. u138 34:41 >> Em
139. u139 34:42 >> No, naj govorim o
140. u140 34:43 >> Mislim število omejitev, ki jih dobite.
141. u141 34:46 >> Ja.
142. u142 34:46 >> Torej naivno, za vsak odvod imate n s strešico in potem L vrednotenj.
143. u143 34:51 >> Ja, tukaj dobim n s strešico odvodov, tukaj n s strešico, tukaj n s strešico. Skupaj je to n s strešico krat L.
144. u144 34:56 >> Ja. Prav, še en [prhne]
145. u145 34:59 >> Ja.
146. u146 35:00 >> Em
147. u147 35:01 >> O času bom govoril čez sekundo. Morda je jasno, ampak kar povejte.
148. u148 35:04 >> Preverite. Ali to odgovori na vaše vprašanje?
149. u149 35:12 >> Prav, razmislite. Dokončal bom čas. Ja. Torej vse lahko rešimo, če za vsako od L točk izračunamo n s strešico odvodov. Najprej, ni jih prav veliko. N s strešico krat L je približno n. Torej času izvajanja dodamo faktor n.
150. u150 35:28 To je povsem zanemarljivo. Glavna težava je izračun katerega koli od teh odvodov. Vse dražji so, večji kot je K, ampak tukaj lahko preprosto vstavimo K enako n s strešico, da dobimo glavni čas izvajanja. Torej sem skoraj končal.
151. u151 35:45 Čas izvajanja je odvisen predvsem od primera, ko je K enak n s strešico, torej je dve na n skozi polilog n. To je zanemarljivo. Krat n skozi n s strešico na potenco reda n s strešico.
152. u152 36:07 In zdaj nam gre odlično. N skozi n s strešico je približno logaritemsko. Ko to prenesete v eksponent, je dvojno logaritemsko. Torej je to v bistvu dve na red n s strešico krat nekaj faktorjev log log. In n s strešico je n skozi koren iz log n.
153. u153 36:29 Ja.
154. u154 36:29 >> Ali je prav razmišljati, da je računanje vseh teh odvodov nekako lažje kot povečanje L, in če je, zakaj?
155. u155 36:36 >> Odlično. Ja. Lahko bi rekli: »Zakaj smo to tako zastavili? Morda bi lahko dobili precej večji L in bi morali izračunati manj odvodov. To bi bilo dobro.«
156. u156 36:54 Odlično vprašanje. Bistvo je, mislim, kot bomo upam videli ali začeli spoznavati, da je že to nekako težko doseči. Morda je najtežje sploh dobiti velik L. In pri našem pristopu nikoli ne boste mogli dobiti L, večjega od log n.
157. u157 37:12 Torej bomo morda kmalu videli motivacijo. Pri tem celotnem pristopu nikoli ne boste dobili L, večjega od približno log n. To morate torej preprosto sprejeti, potem pa si rečete: moja stopnja je tako velika, dobim pa lahko samo L, log n.
158. u158 37:29 Takrat najprej pomislite: morda lahko dobim odvode, da bom imel dovolj podatkov, in to se izide, potem pa upajmo, da odvodov ni pretežko izračunati, in tudi to se ravno še izide. Pravzaprav bomo to morda poskusili motivirati s primerom, kjer je L dobesedno ena.
159. u159 37:48 Imeli bomo samo A0, težko stvar, ki jo poskušamo izračunati, in sestavili A1, ki ga je zelo lahko izračunati. Izra- izračunljiv je v času približno dve na koren iz n, kar je precej bolje. V nekem smislu bomo med njima lahko interpolirali, ampak L enako ena je tako malo, da boste potrebovali v bistvu vse odvode in ne boste dobili nobene pohitritve.
160. u160 38:14 Lepota je torej morda v tem, da bomo lahko L nekoliko povečali, da bo število odvodov nekoliko manjše od n. In [prhne] mislim, da se bo pokazalo še nekaj, ko bom morda govoril o primeru L enako ena.
161. u161 38:31 Kot sem rekel, te permanente bomo lahko izračunali v času približno dve na koren iz n, in to je skoraj predobro. Veste, da niste na pravi poti, ker je dve na koren iz n prehitro. Uporabili bomo dejstvo, da nas ne bi motilo, če bi lahko permanent A I izračunali zgolj v času dve na N skozi polilog N.
162. u162 38:48 To bi bilo povsem v redu. Če si dovolimo to šibkost, bomo lahko dobili bolj strukturirane A I, ki jih lahko uporabimo za naš interpolacijski načrt. Prav. Kakšno vprašanje? Prav.
163. u163 39:08 Prav, to je dobra točka za premor. Naj poskusim ugotoviti, kaj povedati naprej. Ja.
164. u164 39:18 >> Rad bi postavil zelo podobno vprašanje. Rekli ste, da je bila ta tako imenovana relacija dovoljenja že znana v teoretičnem računalništvu.
165. u165 39:25 >> Ja.
166. u166 39:26 >> Bolj na splošno me zanima, zakaj bi bilo pridobivanje podatkov iz odvodov lahko kaj lažje od pridobivanja iz drugih točk ničtega reda
167. u167 39:39 >> Pridobivanja na različnih mestih?
168. u168 39:42 >> Da.
169. u169 39:43 >> Ja, dobro vprašanje. Zgodilo se bo nekako to, da bomo zgradili matrike A I, ki so na neki način podobne A, ampak imajo veliko dobre strukture, in uspelo nam jih bo narediti samo logaritemsko mnogo. Zato želimo iz teh krasnih strukturiranih A I iztisniti čim več.
170. u170 40:03 In to je tukaj motivacija, zakaj rečemo: potrebujem jih več. Zato bom poleg permanentov poskusil izračunati še te odvode. Morda bom zdaj omenil, ker se ne bomo spuščali v podrobnosti, naslednje.
171. u171 40:22 A I bo zelo strukturiran, kot bomo videli čez trenutek, zato lahko njegov permanent učinkovito izračunamo. Kako izračunamo odvode permanenta na teh različnih me- strukturiranih mestih A I?
172. u172 40:45 Prav, to je nekakšna domača naloga za nekoga, ki je dober v algebraični zahtevnosti ali algebri permanentov ali pozna stvari, recimo zna zapisati formulo za permanent vsote dveh matrik.
173. u173 41:02 Nekako vidite, da za izračun K-tega odvoda permanenta pri A I potrebujete, zadostuje, da znate izračunati permanente množice podmatrik A I.
174. u174 41:23 In to je nekakšna preprosta lastnost permanenta. Zato sem to dodal. Hotel sem opozoriti, da A I ni samo dovolj strukturiran, da hitro izračunate njegov permanent, ampak lahko hitro izračunate tudi permanent katere koli podmatrike. Za izračun K-tega odvoda morate, če pogledate podrobnosti, izračunati nekako vse permanente podmatrik K krat K ali nekaj takega, morda glavnih podmatrik tega A I.
175. u175 41:55 In tukaj to pride prav. Torej vse te lahko hitro izračunamo zaradi tega. Koliko pa je glavnih podmatrik K krat K? Približno N nad K, zato je tukaj ta N nad K. To je vse, kar bom v nadaljevanju povedal o računanju odvodov.
176. u176 42:13 Ja.
177. u177 42:13 >> Če lahko dobite L točk, zakaj potem to pomeni, da lahko K postane nič?
178. u178 42:18 >> Zato ker imajo pri tej postavitvi, kot bomo videli, A1 do AL zelo prijetno strukturo. Povedal bom čez trenutek. Skoraj bločno diagonalne so in zato je njihove permanente zelo lahko izračunati. A0 pa je samo prvotna grozna, grozna nestrukturirana matrika.
179. u179 42:37 Zato je sploh ne znate učinkovito izračunati. Ja. Celotna igra je torej narediti A1 do AL dovolj strukturirane, da jih lahko učinkovito izračunate, v podeksponentnem času, in hkrati tako, da z interpolacijo skozi njih dobite permanent A0, ki je zelo nestrukturirana matrika.
180. u180 43:00 Prav, pogovorimo se o strukturi, ki jo bodo imeli A I in zaradi katere jih bo lahko izračunati. Zakaj bodo A I nekoliko lažji?
181. u181 43:30 >> [aplavz]
182. u182 43:33 >> To seveda za I večji od nič. No, I in L. Prav. Na grobo skoraj zato, ker bodo videti takole. Bločno diagonalni bodo. Prav, takole bodo bločno diagonalni.
183. u183 43:59 Prav, malo lažem. Laž bom pojasnil čez trenutek. Naj to matriko poimenujem B. A I ne bo čisto takšen kot B, ampak naj povem to. Poleg tega bodo vse te dimenzije približno n skozi, tukaj lahko postavite kateri koli polilog.
184. u184 44:22 Morda torej n skozi log na deseto n. Aha, povedati moram, da bodo imele to poli- to bločno diagonalno strukturo, ko ustrezno preuredite vrstice in stolpce. Pravzaprav vas lahko vprašam.
185. u185 44:39 Zakaj ste zelo veseli, ko morate računati permanent teh matrik? Matrik, ki so videti takole?
186. u186 44:47 >> Ker računanje permanenta gre pri n skozi polilog, kar je dve na n skozi polilog.
187. u187 44:53 >> Ja, permanent bločno diagonalne matrike, kakršna je ta, je tako kot determinanta, ali pa se spomnite, kako permanent deluje. Permanent celote je permanent tega bloka krat permanent tega bloka krat permanent tega bloka krat permanent tega bloka in tako naprej. In koliko časa potrebujemo za permanent tega bloka?
188. u188 45:13 Uporabimo to. Torej dve na dimenzijo, ki je, kar koli, n skozi polilog n. Vse te lahko torej izračunamo v tem zelo »hitrem« času.
189. u189 45:29 In potem, ne vem, manj jih je od tega. Mislim, da jih je logaritemsko, polilogaritemsko mnogo. Rezultate samo zmnožimo. Če bi bil A I tako čudovito strukturiran na ta bločni način, bi to vsekakor imeli. Ne bo čisto tak, bo pa blizu.
190. u190 45:51 A I bo oblike takšnega bloka plus matrika napake. Takole, in ta matrika napake bo imela rang največ n skozi neki velik polilog n.
191. u191 46:16 Vprašal vas bom torej: »Predstavljajte si, da bločno diagonalnega dela ni in je A I samo ta matrika nizkega ranga. Zakaj bi bili veseli, da morate izračunati njen permanent?« Prav, dobro.
192. u192 46:40 Tudi jaz nisem vedel, ampak vsak, ki kaj ve o algebraični zahtevnosti ali podobnih stvareh, bi vedel, da je to staro in ne prav težko dejstvo. Morda ga je prvi dokazal Barvinok, ampak mislim, da ni zelo težko: tudi permanent matrik nizkega ranga lahko učinkovito izračunate.
193. u193 46:59 Torej lahko poleg tega dejstva tudi rang R obdelate v času N na red R. Pravzaprav lahko, če ste nekoliko pazljivi, to naredite v času N plus R nad R.
194. u194 47:30 In na ta način to nekako zajema tudi tisto, ker je največji možni rang N, potem pa dobite 2N nad N, kar je približno 4 na N. Torej je pravzaprav slabše. To je dve na N, to pa štiri na N. Ampak pri tem algoritmu nas pri eksponentnih izrazih konstantni faktor tukaj zgoraj ne moti.
195. u195 47:52 Zato je tudi to v redu. Ja, to je bila stranska pripomba. Ni pomembno. Lahko bi vprašali: »Kako pa to naredite?« In o tem vam nočem govoriti, ker je to staro, dobro znano dejstvo. Ampak povedal bom, da lahko to naredite tudi z dinamičnim programiranjem. In povedal bom celo droben, naj vam samo zastavim to kot majhno vajo.
196. u196 48:16 Kaj pomeni, da ima A rang, rang A je enak R? Pomeni samo, da lahko A zapišemo kot vsoto R matrik ranga ena, ki so zunanji produkti.
197. u197 48:41 Če se spomnite linearne algebre, je videti takole. Ali če je vse kombinatorično, ničle in enice ter dvodelna prirejanja, prav, potem pa pustimo to. Ampak prav.
198. u198 48:58 Če imate matriko ranga ena, to samo pomeni, da je element IJ enak UI krat VJ. In to je res lahka vaja. Zagotavljam vam, da lahko pri takšni matriki, če poznate U in V, njen permanent izračunate povsem trivialno.
199. u199 49:20 In potem, v redu, če je v splošnem videti kot plus UI prime VI prime, je to primer ranga dve. Zdaj morate že malo razmišljati in uporabiti svoje veščine dinamičnega programiranja, ampak bi šlo. Torej si bomo zapomnili tudi to dejstvo.
200. u200 49:39 Ja.
201. u201 49:41 >> Ali mora biti ta polilog večji od ena, mislim eksponent? Sicer pa
202. u202 49:46 >> Aja, ja, ja, ja. Kadar tukaj na tem predavanju pišem polilog, mislim logaritem na neko veliko potenco, ki jo lahko sami določite. Če torej potenca logaritma za vas ni dovolj visoka, lahko prilagodite kon- konstante drugje, da bo tako velika, kot želite.
203. u203 50:03 Torej lahko morda to naredimo ... Pravzaprav, v redu, za tega bom celo rekel, da uredite tako, da je log na 100 od n. To je tisti polilog, za katerega želite, da je največji. Em, v redu.
204. u204 50:18 Torej, rekel sem, da če bi bil AI tako prijazen, da bi bil videti kot ta bločna matrika, bi lahko njegovo permanento izračunali zelo učinkovito. Če pa bi bil AI tako prijazen, da bi bil videti kot ta napaka, kot matrika nizkega ranga, bi jo lahko izračunali učinkovito, ker ... No, tega nisem povedal, ampak to bi naredili v času n na potenco reda n deljeno z log na 100 od n.
205. u205 50:39 To je torej dva na potenco reda n deljeno z log na 99 od n, kar je še vedno odlično. Ampak dejansko bo te oblike, B plus E.
206. u206 50:52 >> [se odkašlja]
207. u207 50:53 >> Zdaj se torej vprašate: aha, ali lahko to združimo? Če imam bločno diagonalno matriko z, saj veste, nekoliko majhnimi bloki plus matriko nizkega ranga. Ali lahko tudi to izračunam v času približno dva na potenco n deljeno s polilogom? Da.
208. u208 51:10 To je še ena vaja. Vse, kar ste naredili tukaj, je bilo z dinamičnim programiranjem, in če torej vse združite, lahko, če je velikost bloka S in rang R, s povezovanjem teh idej izračunate permanento B plus E v času približno dva na potenco reda S krat N na potenco reda R.
209. u209 51:42 V redu? To bo torej naša končna predstava lepo strukturirane matrike. Bločno diagonalna z ne prevelikimi bloki plus napaka nizkega ranga. Te stvari so ravno dovolj strukturirane, da lahko njihove permanente izračunamo res hitro.
210. u210 52:00 Res hitro pomeni dva na potenco n deljeno z velikim polilogom. Em, v redu. Še manjša opomba, in ne spomnim se, ali je pomembna ali ne, ampak drži.
211. u211 52:16 Torej, kaj se tukaj v resnici dogaja? Naj to pobrišem. Oh. V redu. Da izpolnimo vse obveznosti, naj bi znali to narediti tudi za poljubno podmatriko AI. Ampak to je pravzaprav čisto v redu, ker je razred bločno diagonalnih matrik plus matrik nizkega ranga zaprt za jemanje podmatrik.
212. u212 52:38 Če vzamete podmatrike, je struktura še vedno bločna, rang pa se lahko samo zmanjša. Zato velja tudi ta stvar s podmatrikami. V redu. Pravzaprav naj rečem kar to.
213. u213 53:03 Em, kar je, predvidevam, preprosto to, da je za I, ki ni nič, AI lepo strukturiran kot, no, v tej obliki BI plus E.
214. u214 53:26 V redu, kjer je rang E največ N deljeno s polilogom in velikost blokov B prav tako največ N deljeno s polilogom. In ta malenkost, za katero se ne spomnim, ali je pomembna ali ne, je, da je E dejansko isti za vsak I.
215. u215 53:47 Mislim, mislim, da ni pomembno. V redu, to je torej v nekem smislu novi načrt. Ima kdo na tej točki kakšno vprašanje? V redu.
216. u216 54:04 Tukaj se zelo rad ustavim in kar končam, ker si mislim: »V redu, to je kul načrt.« Naslednji del pa je: »V redu, ugotoviti moramo, kako narediti polinomsko družino matrik, ki se pri nič ujema z nestrukturirano A, pri preostalih pa ima to lepo, lepo strukturo.« Po eni strani se tukaj pojavi tista kul ideja, če sploh je kakšna kul ideja.
217. u217 54:26 Po drugi strani pa je postavitev precej kočljiva in to je del, ki ga imam večinoma v glavi, ampak bojim se, da se bom zataknil in kaj zamočil, ampak to bomo zdaj naredili.
218. u218 54:39 >> [prhne]
219. u219 54:39 >> Em, v redu. Kakšno vprašanje? Pravzaprav, ker me je strah, saj veste, da bom kaj zamočil in zabredel v zmešnjavo, v kateri se bom zmedel, naj nekoliko brez motivacije navedem še eno, no, morda ključno bistveno sestavino, ki nam pri tem pomaga.
220. u220 55:02 Tako boste vsaj videli to lepo trditev, ki jo razumem. Potem pa bomo videli, ali lahko govorimo o tem, kako vse skupaj sestaviti. Em.
221. u221 55:12 >> [prhne]
222. u222 55:12 >> Ja. V redu. Kaj je torej ta druga lepa trditev? Samo v mislih poskušam skicirati način, kako bi to povedal.
223. u223 55:36 Em, v redu. Ključna osrednja, osrednja sestavina dokaza je nekaj, kar bi v analizi Boolovih funkcij ali teoriji zahtevnosti veljalo za splošno znano dejstvo.
224. u224 55:55 Pravzaprav smo v bistvu že videli natanko to dejstvo. Nisem ga izrecno navedel v tej obliki, ampak bilo je natanko tisto ključno dejstvo v ozadju, ki smo ga uporabili v dokazu Razborova in Smolenskega, da AC-ji, da, no, pri nas, da večinska funkcija zahteva vezja konstantne globine eksponentne velikosti.
225. u225 56:18 Em, ko smo dokazovali, da večinska funkcija ne more biti ... V redu, naj preskočim, kaj smo govorili, ampak to je bila ključna, em, ključna sestavina tistega dela. Gre pa za računanje FUNKCIJE PARNOSTI NA, EM, L bitih s polinomom nizke STOPNJE.
226. u226 57:00 V REDU? ZELO ME OBREMENJUJE, DA ne rečem parnost na N bitih. Ker ko delaš, kaj vem, analizo Boolovih funkcij, bi moralo biti število bitov N, ampak je prepozno. N je ta n, zato moramo ... to je ta l. Em, v redu.
227. u227 57:19 In upam, da boste med tem začeli opažati nekakšno ujemanje vzorcev med tem in tem. Potem pa moramo to ujemanje vzorcev še dopolniti. Em, v redu, naj malo podrobneje povem, kaj s tem mislim. Pravzaprav smo govorili o ... V redu, ni važno.
228. u228 57:40 Torej bomo pri teh stvareh bite predstavljali s plus ali minus ena namesto z nič in ena. V REDU, TO JE ČISTO V REDU. TO JE SAMO DOGOVOR. IN TE SI PREDSTAVLJAMO KOT realna ali racionalna števila.
229. u229 57:59 V redu, potem imamo funkcijo parnosti na n bitih, l bitih. Vidite, že mešam. Em, x ena do x l. In to lahko izrazimo kot zelo preprost realni polinom več spremenljivk v x ena do x n, kadar uporabljamo zapis, v katerem plus ali minus ena pomenita resnično in neresnično.
230. u230 58:23 Bi mi kdo povedal, kakšen je? Ja, preprosto njihov produkt.
231. u231 58:31 >> [aplavz]
232. u232 58:33 >> To samo kaže, kako pomembno je, nad katerim poljem delate. Če na primer bite predstavljate z nič in ena ter delate nad poljem po modulu dve, ima parnost polinom stopnje ena. Preprosto seštejete bite po modulu dve. Toda v tem svetu, kjer uporabljate plus ali minus ena kot realna števila in poskušate izračunati parnost, ima parnost na l bitih polinom največje možne stopnje, x ena, produkt x ena do x l.
233. u233 59:00 Em, pravzaprav vsaka ... Mislim, to je preprosto dejstvo. Mislim, da smo o tem že govorili, ampak vsaka funkcija, ki preslika n bitov v realna števila, ima polinomsko predstavitev stopnje največ L.
234. u234 59:19 Pravzaprav zato, ker jo lahko interpolirate z nekim polinomom in nikoli ne potrebujete xi na kvadrat ali xi na kub ali xi na četrto, ker če vas zanimajo samo vhodi plus ali minus ena, je xi na kvadrat preprosto ena. Torej mora biti polinom samo multilinearen, zato nikoli ne bo imel stopnje več kot L. Parnost pa potrebuje največjo stopnjo L.
235. u235 59:36 Je nekako najbolj zapletena funkcija z vidika stopnje. Toda ključna ideja, ki jo želimo uporabiti, pravi, da jo lahko nekako izračunamo s polinomom precej nižje stopnje.
236. u236 59:55 No, izračunali jo bomo približno. Em, v redu. In, em ...
237. u237 1:00:09 >> [prhne]
238. u238 1:00:12 >> Drugo vprašanje je, v kakšnem smislu jo bomo približno izračunali. Ker obstajajo različni pojmi tega, da en polinom približno izračuna drugega. Torej bomo iskali, recimo, polinom, em, polinom n spremenljivk, L spremenljivk, recimo G od X1 do XL nizke stopnje D, in ta D bo ta D.
239. u239 1:00:46 Em, pravzaprav sem pozabil, kaj se tukaj dogaja. Morda je takole. Bistvo je, da se spomnite L, v redu, tukaj ni zapisan, ampak L je bil, če se spomnite, nekaj takega kot log n. Torej je D nekaj takega kot kvadratni koren L.
240. u240 1:01:03 In to je vir našega prihranka, dejstvo, da ... oziroma moral bi reči, da je vir prihranka to, da nam uspe narediti ta D opazno manjši od L. Nekako bi bilo trivialno, če bi bil ta D lahko L, ampak mora biti manjši od L, in dejstvo, da ga zmanjšamo za faktor koren iz log n, je tisto, od koder izvira ves prihranek.
241. u241 1:01:22 To se tukaj dogaja. Torej bo ta D, saj veste, 100 koren L log L, kar je, em, recimo epsilon blizu parnosti.
242. u242 1:01:54 Em, in povedal bom, kaj [prhne] s tem mislim. Najprej, epsilon bo 1 deljeno z L na 100. Torej zelo majhen, kot 1 deljeno z ... V redu, ne vem, ali so te stotice enake, ampak ni važno. Em, blizu so.
243. u243 1:02:10 Zelo majhen, kot 1 deljeno z inverznim polinomom. To pa pomeni, da je verjetnost po naključnem X, da se G od X razlikuje od parnosti L od X, največ epsilon.
244. u244 1:02:27 To je nekakšen pojem bližine v smislu L0 ali Hammingove razdalje. Torej bo ta G na večini vhodnih nizov povsem pravilen. Na deležu 1 minus epsilon.
245. u245 1:02:43 >> [prhne]
246. u246 1:02:43 >> Na preostalem deležu epsilon pa je lahko povsem mimo. Lahko je neka nora številka, velikanska številka. Morda ni plus ali minus ena. Bo neko čudaško racionalno število. Ampak to je v redu. In to [prhne] bo vir ... Ta napaka bo vir te zgodbe z rangom.
247. u247 1:03:17 Em, [prhne] ne morem ... Težko se spustim v to. Čas imam omejen, ampak na visoki ravni: če pogledate resničnostno tabelo G minus parnost L, ima samo epsilon krat dva na L neničelnih vrednosti.
248. u248 1:03:43 Pravim resničnostna tabela, čeprav pravzaprav od funkcije s poljubnimi vrednostmi odštevam funkcijo z vrednostmi plus ali minus ena, ampak v tabeli vrednosti to pomeni natanko to, da so večinoma ničle, razen na epsilon krat dva na L mestih. Oziroma na takem deležu mest.
249. u249 1:04:00 In upam, da vam to malo diši po rangu. Nekako uporabljamo dejstvo, da če imate dia- ... To ne bo imelo smisla, ampak poskušam vam dati občutek. Če imate diagonalno matriko, kjer so večinoma ničle, tu in tam pa kakšna zvezdica, je rang te matrike enak številu zvezdic.
250. u250 1:04:25 In zvezdice bodo ustrezale tem mestom, kjer se resničnostni tabeli razlikujeta. To je samo za občutek. Za zdaj vam še ne more biti zares smiselno. Em, v redu. Bistvo pa je, da je delež napake oziroma relativni rang približno ena deljeno z L na neko veliko potenco, 100.
251. u251 1:04:48 In ne pozabite, L je nekako log N.
252. u252 1:04:50 >> [prhne]
253. u253 1:04:50 >> Torej prav od tod izvira ta log N tukaj. To je v bistvu celo N log na 100 od N. V redu, [prhne] dejstvo, da je ta relativni rang približno ena deljeno z log na 100 od N, bo izviralo natanko iz tega, da je bil delež napake približno ena deljeno z L na 100.
254. u254 1:05:14 Ampak tega še ne morete videti, ker tudi ne bomo imeli časa zares pojasniti, kako se bo ta sestavina preslikala v to sestavino, ampak ... Lahko si preberete več ali pa, ne vem, morda bom naredil kak dodaten video, kjer dokončam skico, ali kaj takega, ampak v redu, vrnimo se k temu osnovnemu, kaj vem, problemu iz analize Boolovih funkcij.
255. u255 1:05:41 In, saj veste, če ste pravi navdušenec nad teoretičnim računalništvom, morda že natanko veste, kako to rešiti, ampak vam bom pokazal. Em, v redu, torej, ja, če ste ... Vsi ti polinomi, ki nas zanimajo, imajo nekako stopnjo do L.
256. u256 1:06:00 Parnost ima stopnjo natanko L, mi pa poskušamo njene vrednosti ujeti s polinomom precej nižje stopnje. Kakšna je torej ideja? Eden od vidikov, ki bo pomemben, je, da je parnost simetrična funkcija. Njena vrednost je odvisna samo od Hammingove teže vhoda.
257. u257 1:06:20 Drugače povedano, to se bo še pojavilo: parnost L od X ena do XL je odvisna samo od X ena plus tri pike plus XL.
258. u258 1:06:40 To ni natanko Hammingova teža, ker uporabljamo zapis s plus ali minus ena. Če bi uporabljali zapis z nič in ena, bi to bila Hammingova teža. Ampak v redu, do nekega linearnega premika je enako kot Hammingova teža. Če seštejete pluse ali minuse ena, vam to pove Hammingovo težo.
259. u259 1:06:54 >> [prhne]
260. u260 1:06:56 >> Em, in na splošno, če vas zanimajo simetrične funkcije na ... Tukaj bi moral biti L. Em, na plus ali minus ena na L.
261. u261 1:07:06 >> [prhne]
262. u262 1:07:07 >> Em, lahko jih izrazimo kot ... Tudi to je zelo preprosto. Lahko jih izrazimo kot
263. u263 1:07:18 >> [aplavz]
264. u264 1:07:20 >> polinom ene spremenljivke P v X ena plus tri pike plus XL. Seveda bo vsaka funkcija iz L-bitnih nizov v R, ki jo lahko izrazite kot polinom ene spremenljivke, uporabljen na vsoti X1 do XL, simetrična, ker se vsota ne spremeni, če permutirate XI-je.
265. u265 1:07:48 Nekaj dela je treba, da vidimo obratno smer, da je torej vsako tako simetrično Boolovo funkcijo mogoče izraziti kot polinom ene spremenljivke, uporabljen na vsoti, ampak ni težko. To je povezano tudi s Trevorjevim videom, kjer je govoril o simetričnih funkcijah.
266. u266 1:08:06 Ampak je v tem primeru malo lažje. In tudi stopnja tega polinoma P bo enaka stopnji vaše simetrične funkcije kot polinoma več spremenljivk. Ker tukaj vzamete nekaj stopnje ena in to vstavite v polinom P neke stopnje D, boste dobili polinom več spremenljivk stopnje D.
267. u267 1:08:29 Torej to posebej pove, da lahko parnost tako izrazimo z nekim čudnim polinomom P stopnje L. In to je res precej čuden polinom. Videti je precej lepše, ko ga zapišete tako, ampak je mogoče. Poskusimo narisati sliko.
268. u268 1:08:48 Em, tako nekateri radi rišejo Boolovo kocko, hiperkocko. To je slika 01 na L ali plus ali minus ena na L, pri kateri Hammingova teža narašča navzgor.
269. u269 1:09:08 Torej je to Hammingova teža ... Sliko bom čez trenutek pojasnil, če je še niste videli. Hammingova teža L ali enakovredno vsota XI je enaka plus L. Morda sem ... Kakorkoli, ne zanemarjam, ali nič pomeni plus in ena minus ali obratno.
270. u270 1:09:24 To je Hammingova teža nič, kar je enakovredno temu, da je vsota xi enaka minus L. To je Hammingova teža L deljeno z dve, kar je enakovredno temu, da je vsota xi enaka nič, in tako naprej.
271. u271 1:09:42 V redu, narisano je na ta čuden način, da vas spomni, da je med vsemi dva na L nizi tukaj en sam tukaj in en sam tukaj. Na naslednji ravni s Hammingovo težo L minus ena jih je zelo malo. Pravzaprav jih je L. In tudi tukaj jih je zelo malo pri ... Tukaj pri Hammingovi teži L minus dve jih je morda L nad dve.
272. u272 1:10:04 Ampak vse dogajanje je tukaj, ko ste okoli srednje Hammingove teže. Prav tukaj jih je natanko L nad L deljeno z dve, kar je zelo blizu dva na L deljeno s korenom L. In vse ravni, torej ta delež prav na sredini oziroma ta raven prav na sredini vsebuje delež ena deljeno s korenom L vseh nizov.
273. u273 1:10:33 In naslednja pri Hammingovi teži L deljeno z dve plus ena prav tako, če malo poračunate, vsebuje v bistvu delež ena deljeno s korenom L vseh nizov. Enako velja za vse tiste čisto blizu srednjih plasti. In posebej lahko dobite skoraj vse Boolove nize že, če greste do Hammingove teže L deljeno z dve plus ali minus koren L.
274. u274 1:11:02 No, če greste do L deljeno z dve plus ali minus približno 50 koren L, boste dobili približno 99,999999 % vseh nizov. In če greste do L deljeno z dve plus ta količina, torej L deljeno z dve plus ali minus D, kjer je D koren L krat koren log L, potem s preprostim izračunom z uporabo, kaj vem, Chernoffove meje ali česa podobnega, dobimo dobro znano dejstvo, da te ravni vsebujejo delež 1 minus 1 deljeno z L na 100 VSEH NIZOV.
275. u275 1:11:45 V REDU, TOREJ SE SKORAJ VSE DOGAJANJE V BOOLOVI KOCKI dogaja znotraj te ravni. In kaj se dogaja s parnostjo? Ne pozabite, parnost je simetrična funkcija. Torej je vrednost parnosti pri poljubni Hammingovi teži oziroma je odvisna samo od Hammingove teže.
276. u276 1:12:05 Parnost ima to lastnost, da je plus ena ... V redu, na srednji plasti ima neko vrednost plus ena ali minus ena, odvisno od parnosti L deljeno z 2. Potem je na naslednji plasti minus ena, na naslednji plus ena, minus ena, minus ena. Torej izmenjuje cele pasove od spodaj navzgor.
277. u277 1:12:24 In to je parnost. Em, naš cilj je torej dobiti to funkcijo G ali F, G, ne vem, zakaj sem to napisal. Ja, G, ki večinoma pravilno zadene parnost.
278. u278 1:12:42 In G naj bi imel nizko stopnjo. Sam G bomo vzeli simetričen. Torej bomo želeli, da je G ... Škoda. G bomo vzeli v obliki, em ...
279. u279 1:13:03 >> [aplavz]
280. u280 1:13:04 >> nekega polinoma ene spremenljivke Q, uporabljenega na X1 plus tri pike plus XL. In naš načrt bo preprosto ... V redu, zdaj bo ta polinom ene spremenljivke Q videti takole.
281. u281 1:13:28 Želimo, da je videti takole. Tukaj je L. To je slika polinoma ene spremenljivke, L minus 1, L deljeno z 2, 0. Aha, v redu. Ni važno. Pravzaprav bo plus L, minus L, 0, 1 ali morda 2, minus 2, nekaj takega.
282. u282 1:13:54 Em, parnost ... Ta čudni P za parnost, ki deluje za parnost, je natanko polinom, ki je morda plus 1 pri 0, potem minus 1 pri 2, potem plus 1 in minus 1, plus 1, minus 1.
283. u283 1:14:14 Videti je takole. To je P za parnost in je precej nora funkcija. V redu, to je P za parnost. Je neki polinom ene spremenljivke stopnje L, ki gre natanko skozi plus 1, potem minus 1, potem plus 1, potem minus 1, potem plus 1, potem minus 1.
284. u284 1:14:36 In vidite, da ko v P vstavite nekaj teh X I-jev, dobite polinom več spremenljivk, ki je natanko, saj veste, plus 1, minus 1, plus 1, minus 1, plus 1, minus 1. In je povsod popoln. No, povsod je parnost. Em, v redu, poskusili bomo narediti nekaj podobnega, le da bomo uporabili ta ... Uporabili bomo Q, ki mora imeti precej nižjo stopnjo, ampak upam, da je načrt očiten.
285. u285 1:15:04 Te pluse ali minuse 1 bomo pravilno zadeli samo v tem okvirju tukaj s širino, saj veste, D je enako koren L log L. Torej želimo polinom Q, polinom ene spremenljivke, ki se ujema s tem plus 1, minus 1, plus 1, minus 1, plus 1, minus 1 samo v tem okvirju širine D.
286. u286 1:15:27 In spet, za poljubno množico D ali D plus 1 ali D minus 1 točk, kolikor jih pač želite, lahko natančno interpolirate s polinomom ene spremenljivke stopnje D. Tako bo tisti za Q natanko zadel vse te točke.
287. u287 1:15:45 Ko ste zunaj tega okvirja, bo morda zavil v drugo smer kot P za parnost, ampak to nas ne zanima. Bistvo je, da bo Q res imel stopnjo samo koren log L. In s parnostjo se bo ujemal na vseh teh srednjih plasteh. Potem pa ima lahko zunaj tukaj povsem poljubne vrednosti.
288. u288 1:16:04 Ampak te nas ne zanimajo, ker predstavljajo samo delež ena deljeno s poli L kocke. Torej, odličen trenutek za povzetek. Nismo torej videli, kako to narediti.
289. u289 1:16:21 Mislim, to je še vedno načrt. In ta načrt bomo uresničili s tem ključnim splošno znanim dejstvom. Em, [prhne] ali lahko o tem kaj povem v približno 1 minuti? Morda ne bom zares poskušal kaj povedati o tem v 1 minuti.
290. u290 1:16:46 No, v redu, povedal bom eno malenkost. Samo eno malenkost o tem, kakšni so ti AI-ji.
291. u291 1:17:04 >> [prhne]
292. u292 1:17:04 >> Em, težko je sploh povedati, ampak čisto naslednja stvar, ki bi jo naredili, če bi imel več časa, je ...
293. u293 1:17:10 >> [prhne]
294. u294 1:17:10 >> Iz tega G bi sestavil nekaj zelo lepih matrik. Posebej bi sestavil eno lepo matriko, [prhne] Hadamardovo matriko.
295. u295 1:17:28 Em, indeksirano z 0 1 na L oziroma dva na L, krat diagonalna matrika z G krat Hadamardova matrika. To preprosto pomeni, da resničnostno tabelo G, ki ima spet poljubne realne vrednosti, postavim vzdolž diagonale.
296. u296 1:17:53 In, em ...
297. u297 1:17:56 >> [prhne]
298. u298 1:17:57 >> Ta matrika bo zelo dober nadomestek za matriko, ki bi jo dobili, če bi na to diagonalo postavili pluse ali minuse parnosti. Nekako ima precej nižjo stopnjo.
299. u299 1:18:12 >> [prhne]
300. u300 1:18:12 >> In če na to diagonalo postavite elemente plus ali minus ena iz parnosti ter z obeh strani pomnožite s to matriko Hadamardove Fourierove transformacije, dobite antidiagonalno matriko. Kar je pomembno.
301. u301 1:18:32 Navdušenci nad kvantnim računalništvom bodo to prepoznali kot H Z H je enako X v neki tenzorski obliki. Kakorkoli, nekako vzamete svojo A in jo faktorizirate tako, da se pojavi ta antidiagonalna matrika.
302. u302 1:18:52 Potem pa to antidiagonalno matriko zamenjate z nekimi približki, ki so videti takole, zaradi česar dobite bolj strukturirane matrike. Zmanjkalo mi je časa. Tega ne morem prav dobro razložiti. [smeh] To je nekaj sestavin. V redu.
303. u303 1:19:08 [prhne] Končujemo torej zmedeno, ampak ali ima kdo kakšno vprašanje o dokazu ali rezultatih ali čemerkoli? Ja.
304. u304 1:19:16 >> Em, boste dokaz dokončali naslednjo uro?
305. u305 1:19:19 >> Ali bom dokaz dokončal naslednjo uro? To je čudovito vprašanje. Ne vem. Pravzaprav naslednja ura odpade, kajne? Demokracija je. Ne, ja, dan demokracije. Šli bomo volit. Torej to morda poveča možnosti, ker bom imel en teden. Ne vem.
306. u306 1:19:31 >> [smeh]
307. u307 1:19:33 >> NE VEM. ODVISNO JE od vas. Bi radi, da naslednjo uro dokončam dokaz, ali naj se vrnemo k ... V redu, vidim veliko prikimavanja. V redu, naslednjo uro bom dokončal dokaz. Zveni dobro.