Диссертация (1103424), страница 24
Текст из файла (страница 24)
Îáùåå ÷èñëî áèòîâ ýòîãî îïèñàíèÿ íå ïðåâîñõîäèò4 log n + (l1 + l2 + q − m + 1.01) + O(1) < l1 + l2 − δ + (5 − c) log n, ïðè ýòîìèñïîëüçóåìàÿ ïàìÿòü ðàâíà O(s). Òàêèì îáðàçîì, ïðè íàøèõ ïðåäïîëîæåíèÿõCO(s) (x, y) < l1 +l2 −δ +(5−c) log n = Cs (x)+Cs (y)−δ +(5−c) log n, (6.3)116÷òî ïðîòèâîðå÷èò óñëîâèþ Cµs (x, y) > Cs (x) + Cs (y) − δ ïðè c > 5 è äîñòàòî÷íî áîëüøîì µ.Â-òðåòüèõ, äîêàæåì, ÷òî äëÿ T = Gn (uRBT ) âûïîëíåíû ñâîéñòâà óñèëåííîãî êîëìîãîðîâñêîãî ýêñòðàêòîðà. Ïðèâåä¼ì ðàññóæäåíèå òîëüêî äëÿîäíîãî èç óñëîâèé, âòîðîå ïîëó÷èòñÿ ñèììåòðè÷íî.
Ïóñòü äàíû ñëîâà x è yäëèíû n, äëÿ êîòîðûõ Cs (x) = l1 > k , Cs (y) = l2 > k è Cµs (x, y) > l1 +l2 −δ .(Êîíñòàíòà µ íå çàâèñèò îò x è y è áóäåò âûáðàíà ïîçäíåå). Ïðåäïîëîæèì,÷òî äëÿ ýòèõ ñëîâ ñâîéñòâî óñèëåííîãî êîëìîãîðîâñêîãî ýêñòðàêòîðà íåâûïîëíåíî, ò.å. Cs (T (x, y)|x) 6 m − δ − Ω(log n). Ìîæíî ñ÷èòàòü, ÷òî êîíñòàíòà, ñêðûòàÿ â Ω(log n), áîëüøå c, ïîýòîìó Cs (T (x, y)|x) < q . Îïðåäåëèììíîæåñòâà S1 è S2 òàê æå, êàê â ðàññóæäåíèè äëÿ îáû÷íûõ ýêñòðàêòîðîâ,âíîâü ïîëó÷èì, ÷òî (S1 , l1 ) è (S2 , l2 ) ëåæàò â S . Îïðåäåëèì êîðòåæ Q ÷åðåçìíîæåñòâî S1 = {v1 , .
. . , vL } ñîãëàñíî (6.2). Òîãäà, î÷åâèäíî, Q ∈ R. Äàëåå,ðàññìîòðèì äâà ñëó÷àÿ: ëèáî ñóùåñòâóåò áîëüøå 2l2 +q−m+1.01 ñëîâ z ∈ S2 ,óäîâëåòâîðÿþùèõ óñëîâèþ Cs (T (x, z)|x) < q , ëèáî ñóùåñòâóåò íå áîëüøå2l2 +q−m+1.01 òàêèõ ñëîâ. ïåðâîì ñëó÷àå ñòîëáåö {x} × S2 áóäåò íàñûùåííûì, ïîñêîëüêó ñîäåðæèò áîëüøå 2l2 +q−m+1.01 ïîìå÷åííûõ (êàê â îïðåäåëåíèè 6.11) ÿ÷ååê, ïðèýòîì ÿ÷åéêà (x, y) ïîìå÷åíà.  ñèëó (k, q, 1.01, R, S)-ðàâíîìåðíîé ïåñòðîòû òàáëèöû T îáùåå êîëè÷åñòâî ïîìå÷åííûõ ÿ÷ååê â íàñûùåííûõ ñòîëáöàõ íå áîëüøå 2l1 +l2 +q−m+k+1.01 , ÷òî ìåíüøå 2l1 +l2 −δ−c log n+1.01 .
Òàêèì îáðàçîì, ÿ÷åéêà (x, y) ìîæåò áûòü çàäàíà ÷èñëàìè n, l1 , l2 , q è ñâîèì ïîðÿäêîâûì íîìåðîì ñðåäè îòìå÷åííûõ ÿ÷ååê â íàñûùåííûõ ñòîëáöàõ, ïðè÷¼ìäëÿ ïîèñêà (x, y) ïî ýòèì äàííûì òðåáóåòñÿ ïàìÿòü O(s). Òàêèì îáðàçîì,CO(s) (x, y) < 4 log n+l1 +l2 −δ−c log n+1.01+O(1) < l1 +l2 −δ+(5−c) log n,÷òî ïðîòèâîðå÷èò óñëîâèþ Cµs (x, y) > Cs (x) + Cs (y) − δ ïðè c > 5 è äîñòàòî÷íî áîëüøîì µ.Âî âòîðîì ñëó÷àå ïàðà (x, y) ìîæåò áûòü ïîëó÷åíà íà ïàìÿòè O(s), åñëèèçâåñòíû ÷èñëà n, l1 , l2 , q (íå áîëüøå 4 log n áèòîâ), êðàò÷àéøåå îïèñàíèå x(l1 áèòîâ) è íîìåð y ñðåäè ïîìå÷åííûõ ÿ÷ååê â ñòîëáöå {x} × S2 (íå áîëüøål2 + q − m + 1.01 = l2 − δ − c log n + 1.01 áèòîâ).  ñîâîêóïíîñòè ýòè äàííûåçàíèìàþò 4 log n + l1 + l2 − δ − c log n + 1.01 áèòîâ, ò.å.
ìû ïîëó÷àåì òî æåïðîòèâîðå÷èå, ÷òî è â ïåðâîì ñëó÷àå.Òàêèì îáðàçîì, óòâåðæäåíèå ïîëíîñòüþ äîêàçàíî.Äëÿ çàâåðøåíèÿ äîêàçàòåëüñòâà òåîðåìû 6.2 ïðîâåä¼ì îöåíêó ïàðàìåò117ðîâ. Ïî òåîðåìå 6.5 ñóùåñòâóþò ï¼ñòðûå òàáëèöû äëÿ k > m/2 + O(log n) èq > m/2 + O(log n). Ñîãëàñíî óòâåðæäåíèþ 6.9 ñóùåñòâóþò è (k, q, 1, Q, S)ï¼ñòðûå òàáëèöû äëÿ ýòèõ ïàðàìåòðîâ. Çíà÷èò, ïî òåîðåìå 6.18 íàéä¼òñÿ àëãîðèòì, íàõîäÿùèé uBT , äëÿ êîòîðîãî Gn (uBT ) åñòü êîä íåêîòîðîé (k, q, 1.01, Q, S)-ï¼ñòðîé òàáëèöû, à ïî òåîðåìå 6.19 ýòà òàáëèöà ÿâëÿåòñÿ (k, m − q − c log n)-êîëìîãîðîâñêèì ýêñòðàêòîðîì.
Ïóò¼ì íåñëîæíûõ ïðåîáðàçîâàíèé ïîëó÷àåì, ÷òî ãîäÿòñÿ ëþáûå m 6 2k − O(log n) èδ = m − q − c log n 6 m − m/2 − O(log n) − c log n 6 k − O(log n), ÷òîñîîòâåòñòâóåò óòâåðæäåíèþ òåîðåìû 6.2.Àíàëîãè÷íî ïî òåîðåìå 6.5 ñóùåñòâóþò ðàâíîìåðíî ï¼ñòðûå òàáëèöûäëÿ k > m + O(log n) è ëþáîãî q . Ñîãëàñíî óòâåðæäåíèþ 6.13 ñóùåñòâóþò è (k, q, 1.01, R, S)-ðàâíîìåðíî ï¼ñòðûå òàáëèöû äëÿ ýòèõ ïàðàìåòðîâ. Çíà÷èò, ïî òåîðåìå 6.18 íàéä¼òñÿ àëãîðèòì, íàõîäÿùèé uRBT , äëÿêîòîðîãî Gn (uRBT ) åñòü êîä íåêîòîðîé (k, q, 1.01, R, S)-ðàâíîìåðíî ï¼ñòðîé òàáëèöû, à ïî òåîðåìå 6.19 ýòà òàáëèöà ÿâëÿåòñÿ (k, m − q − c log n)êîëìîãîðîâñêèì ýêñòðàêòîðîì â ñèëüíîì ñìûñëå.
Ïóò¼ì íåñëîæíûõ ïðåîáðàçîâàíèé ïîëó÷àåì, ÷òî ãîäÿòñÿ ëþáûå m 6 k − O(log n) è δ =m − q − c log n 6 m − c log n 6 k − O(log n), ÷òî ñîîòâåòñòâóåò óòâåðæäåíèþòåîðåìû 6.2.Òàêèì îáðàçîì, îñíîâíîé ðåçóëüòàò ýòîé ãëàâû òåîðåìà 6.2 ïîëíîñòüþ äîêàçàí.6.6Òåîðåìà äëÿ ìàëûõ îãðàíè÷åíèé íà ïàìÿòüÍàøè àíàëîãè òåîðåìû Ìó÷íèêà áûëè ñôîðìóëèðîâàíû äëÿ ïðîèçâîëüíîãî îãðàíè÷åíèÿ íà ïàìÿòü s, à òåîðåìà 6.2 òîëüêî äëÿ íå ìåíåå ÷åì ïîëèíîìèàëüíîãî, ïðè÷¼ì äîâîëüíî áîëüøîãî. Ýòî ñâÿçàíî ñ äâóìÿ âåùàìè. Âîïåðâûõ, íàõîæäåíèå àðãóìåíòà ãåíåðàòîðà ÍèñàíàÂèãäåðñîíà òðåáóåò ïîëèíîìèàëüíîé ïàìÿòè, ò.å.
äëÿ âû÷èñëåíèÿ ïîñòðîåííîãî êîëìîãîðîâñêîãîýêñòðàêòîðà òðåáóåòñÿ ïîëèíîìèàëüíàÿ ïàìÿòü. Âî-âòîðûõ, ïðîòèâîðå÷èâûå îöåíêè íà ñëîæíîñòü ÿ÷åéêè (x, y) ïîëó÷àþòñÿ òîëüêî ïðè äîñòàòî÷íîáîëüøîì ïîëèíîìèàëüíîì îãðàíè÷åíèè, êîòîðîå òðåáóåòñÿ äëÿ êîðîòêîãîîïèñàíèÿ. Òåì íå ìåíåå, òðåáîâàíèå ïîëèíîìèàëüíîñòè s ìîæíî îñëàáèòüè äîêàçàòü ñëåäóþùåå óñèëåíèå òåîðåìû 6.2. ×òîáû íå ìåíÿòü îïðåäåëåíèå êîëìîãîðîâñêîãî ýêñòðàêòîðà ñ îãðàíè÷åíèåì íà ïàìÿòü, íàïèøåì âñåóòâåðæäåíèÿ ÿâíî.118Òåîðåìà 6.20. Ïóñòü çàäàíû ÷èñëà n, s, k ∈ (1, n) è δ ∈ (1, k − O(log n)).Òîãäà äëÿ íåêîòîðûõ ïîëèíîìîâ p1 (n) è p2 (n) è êîíñòàíòû µ ñóùåñòâóþò ôóíêöèè:• T : {0, 1}n × {0, 1}n → {0, 1}m , ãäå m = 2k − O(log n), âû÷èñëèìàÿíà ïàìÿòè p1 (n), äëÿ êîòîðîé âûïîëíåíî ñëåäóþùåå ñâîéñòâî.
Äëÿëþáûõ ñëîâ x è y äëèíû n, äëÿ êîòîðûõ âûïîëíåíî Cs (x) > k , Cs (y) >k è Cµs+p2 (n) (x, y) > Cs (x) + Cs (y) − δ , âåðíî Cs (T (x, y)) > m − δ −O(log n).• V : {0, 1}n × {0, 1}n → {0, 1}m , ãäå m = k − O(log n), âû÷èñëèìàÿíà ïàìÿòè p1 (n), äëÿ êîòîðîé âûïîëíåíî ñëåäóþùåå ñâîéñòâî. Äëÿëþáûõ ñëîâ x è y äëèíû n, äëÿ êîòîðûõ âûïîëíåíî Cs (x) > k , Cs (y) >k è Cµs+p2 (n) (x, y) > Cs (x) + Cs (y) − δ , âåðíî Cs (V (x, y)|x) > m − δ −O(log n) è Cs (V (x, y)|y) > m − δ − O(log n).Äîêàçàòåëüñòâî. Äîêàçàòåëüñòâî ýòîé òåîðåìû ïîâòîðÿåò îñíîâíûå øàãèäîêàçàòåëüñòâà òåîðåìû 6.2 è èñïîëüçóåò òå æå ëåììû. Ïîýòîìó ìû íå áóäåì åãî ïðèâîäèòü öåëèêîì, à îñòàíîâèìñÿ íà äâóõ îñíîâíûõ îòëè÷èÿõ. Âîïåðâûõ, ïîñêîëüêó s áîëüøå íå îáÿçàíî áûòü ïîëèíîìèàëüíûì, ôóíêöèè Tè V ìîãóò íå áûòü âû÷èñëèìû íà ïàìÿòè O(s).
Ïîýòîìó ìû ââîäèì ïîëèíîìèàëüíîå îãðàíè÷åíèå p1 (n) â ÿâíîì âèäå. Âî-âòîðûõ, ïðè äîêàçàòåëüñòâåàíàëîãà òåîðåìû 6.19 â íåðàâåíñòâå (6.3) áîëüøå íåëüçÿ èñïîëüçîâàòü îãðàíè÷åíèå íà ïàìÿòü O(s), âìåñòî ýòîãî äîëæíî áûòü O(s)+poly(n). Ïîýòîìóïîìèìî êîíñòàíòû µ ìû ââîäèì â ôîðìóëèðîâêó ïîëèíîì p2 (n).Òàêæå ìîæíî çàìåòèòü, ÷òî ëþáàÿ ÿâíàÿ êîìáèíàòîðíàÿ êîíñòðóêöèÿ(ðàâíîìåðíî) ï¼ñòðîé òàáëèöû ïðèâîäèò ê äîêàçàòåëüñòâó òåîðåìû 6.2 (èòåîðåìû 6.20). Îäíàêî, íàñêîëüêî èçâåñòíî àâòîðó, òàêèõ êîíñòðóêöèé ïîêàíå ñîçäàíî.119Çàêëþ÷åíèå ñòàòüå [6] Êîëìîãîðîâ ãîâîðèë î òð¼õ ïîäõîäàõ ê ïîíÿòèþ êîëè÷åñòâîèíôîðìàöèè: êîìáèíàòîðíîì, âåðîÿòíîñòíîì è àëãîðèòìè÷åñêîì. Êàæäûé èç ýòèõ ïîäõîäîâ ïðåäñòàâëÿåò èíòåðåñ è äîâîëüíî ïîäðîáíî èçó÷åí,íî îñîáåííî èíòåðåñíû ñîîòíîøåíèÿ ìåæäó ðàçíûìè ïîäõîäàìè.
 íàñòîÿùåé ðàáîòå ìû óñòàíîâèëè íîâûå ñâÿçè ìåæäó êîìáèíàòîðíûìè è àëãîðèòìè÷åñêèìè óòâåðæäåíèÿìè è ðàçðàáîòàëè íîâûé ñïîñîá ðàñïðîñòðàíåíèÿóòâåðæäåíèé îá îáû÷íîé êîëìîãîðîâñêîé ñëîæíîñòè íà ñëîæíîñòü ñ îãðàíè÷åíèåì íà ðåñóðñû. Îäíàêî ìíîæåñòâî âîïðîñîâ îñòàþòñÿ íåðåø¼ííûìè. Ïðåæäå âñåãî: êàêîâû ïðåäåëû íàøåãî ïîäõîäà? Êàêèå óòâåðæäåíèÿî êîëìîãîðîâñêîé ñëîæíîñòè ìîæíî ïåðåëîæèòü äëÿ ñëîæíîñòè ñ îãðàíè÷åíèåì íà ðåñóðñû ÷åðåç ïîñðåäíè÷åñòâî êîìáèíàòîðíûõ óòâåðæäåíèé?Íàñêîëüêî óíèâåðñàëåí ìåòîä íàèâíîé äåðàíäîìèçàöèè? Ìîæíî ëè äîêàçàòü êàêóþ-ëèáî îáùóþ òåîðåìó íà ýòîò ñ÷¼ò? Ýòè âîïðîñû ÿâëÿþòñÿïðåäìåòîì äàëüíåéøåãî èçó÷åíèÿ.Ïðåäñòàâëÿåò èíòåðåñ âîïðîñ î òîì, ìîæíî ëè ïîñòðîèòü êîëìîãîðîâñêèé àíàëîã äëÿ ýêñòðàêòîðîâ ñ îäíèì èñòî÷íèêîì ïîäîáíî òîìó, êàê êîëìîãîðîâñêèå ýêñòðàêòîðû ïîõîæè íà ýêñòðàêòîðû ñ äâóìÿ èñòî÷íèêàìè.Âîçìîæíî, òåîðåìà Ìó÷íèêà ìîæåò ïðîëèòü ñâåò íà ýòîò âîïðîñ.Åù¼ îäíî âàæíîå íàïðàâëåíèå ðàçâèòèÿ ïîñòðîåíèå ÿâíûõ êîíñòðóêöèé èñïîëüçîâàííûõ íàìè êîìáèíàòîðíûõ îáúåêòîâ.
Íàïðèìåð, ïîñòðîåíèå ÿâíûõ ýêñòðàêòîðîâ ñ îïòèìàëüíûìè ïàðàìåòðàìè ñòàëî áû ïðîðûâîìñðàçó âî ìíîãèõ îáëàñòÿõ. Äëÿ íàøèõ öåëåé èíòåðåñíî áûëî áû ïîñòðîèòüýêñòðàêòîð ñ îïòèìàëüíûìè ïàðàìåòðàìè, âû÷èñëèìûé íà ïîëèíîìèàëüíîé ïàìÿòè: òîãäà áû äëÿ ñîîòâåòñòâóþùåãî àíàëîãà òåîðåìû Ìó÷íèêà íåíóæíî áûëî áû íàèâíîé äåðàíäîìèçàöèè. Âîçìîæíî, íàîáîðîò, ìåòîäîìíàèâíîé äåðàíäîìèçàöèè ìîæíî ïîñòðîèòü òàêîé ýêñòðàêòîð.
Ìîæíî ëèïðè ïîìîùè êàêèõ-ëèáî ÿâíûõ ýêñòðàêòîðîâ äîêàçàòü òåîðåìó Ìó÷íèêàäëÿ îáû÷íîé èëè CBP-ñëîæíîñòè ñ îãðàíè÷åíèåì íà ïàìÿòü âìåñòî CAM120ñëîæíîñòè? Âîçìîæíî, ýòî êàê-òî ñâÿçàíî ñî ñòàíäàðòíûìè òåîðåòèêîñëîæíîñòíûìè ïðåäïîëîæåíèåìè? Òàêæå îòëè÷íûì ðåçóëüòàòîì ñòàëî áûïîñòðîåíèå ïîëèíîìèàëüíî âû÷èñëèìûõ ï¼ñòðûõ òàáëèö: âîçìîæíî, ýòîïîçâîëèëî áû äîêàçàòü ñóùåñòâîâàíèå êîëìîãîðîâñêèõ ýêñòðàêòîðîâ äëÿñëîæíîñòè ñ îãðàíè÷åíèåì íà âðåìÿ (õîòÿ áû äëÿ CAM-ñëîæíîñòè). Òàêæå îòêðûòûì âîïðîñîì îñòà¼òñÿ ñïðàâåäëèâîñòü ãèïîòåçû 5.8 î òåîðåìåÌó÷íèêà ñ äâóìÿ óñëîâèÿìè äëÿ CAM-ñëîæíîñòè.Ìîæíî ñêàçàòü, ÷òî òåîðèÿ êîëìîãîðîâñêîé ñëîæíîñòè ñ îãðàíè÷åíèåì íà ðåñóðñû âñ¼ åù¼ íàõîäèòñÿ â ñòàäèè íàêîïëåíèÿ ôàêòîâ.
Äîâåñòèêîëè÷åñòâî èçâåñòíûõ ðåçóëüòàòîâ äî êðèòè÷åñêîé ìàññû è óëîæèòü èõ âñòðîéíóþ òåîðèþ îñòà¼òñÿ çàäà÷åé áóäóùèõ èññëåäîâàíèé.121Ëèòåðàòóðà1.Àëîí, Í. Âåðîÿòíîñòíûé ìåòîä â êîìáèíàòîðèêå / Í. Àëîí,Äæ. Ñïåíñåð. Ì.: ÁÈÍÎÌ, 2011. 320 c.2.Âåðåùàãèí, Í.Ê. Êîëìîãîðîâñêàÿ ñëîæíîñòü è àëãîðèòìè÷åñêàÿñëó÷àéíîñòü / Í.Ê. Âåðåùàãèí, Â.À. Óñïåíñêèé, À. Øåíü. Ì.: ÌÖÍÌÎ, 2013. 576 c.3.Çâîíêèí, À.Ê. Ñëîæíîñòü êîíå÷íûõ îáúåêòîâ è îáîñíîâàíèå ïîíÿòèéèíôîðìàöèè è ñëó÷àéíîñòè ñ ïîìîùüþ òåîðèè àëãîðèòìîâ / À.Ê.
Çâîíêèí, Ë.À. Ëåâèí // Óñïåõè ìàòåìàòè÷åñêèõ íàóê. 1970. Ò. 25.3. Ñ. 85127.4.Èðõèí, È.À. Ýêñòðàêòîðû è ïî÷òè ýêñòðàêòîðû äëÿ äâóõ èñòî÷íèêîâ: âûïóñêíàÿ êâàëèôèêàöèîííàÿ ðàáîòà / È.À. Èðõèí. Ì.: ÌÔÒÈ,2014. 33 ñ.5.Èöûêñîí,íèÿõ:Ä.Ì.êðàòêèéÂåðîÿòíîñòíûåêîíñïåêòëåêöèéìåòîäû/Ä.Ì.ââû÷èñëåÈöûêñîí.http://logic.pdmi.ras.ru/csclub/sites/default/files/random.pdf 2012.6.Êîëìîãîðîâ, À.Í. Òðè ïîäõîäà ê îïðåäåëåíèþ ïîíÿòèÿ Êîëè÷åñòâî èíôîðìàöèè / À.Í. Êîëìîãîðîâ // Ïðîáëåìû ïåðåäà÷è èíôîðìàöèè. 1965.
Ò.1. 1. Ñ. 311.7.ÌåæäóíàðîäíûéÓñëîâèÿñåäüìîãîòóðíèðÒóðíèðà Ãîðîäîâ,http://www.mccme.ru/turgor/27/ 2006.8.äâàäöàòüìàòåìàòè÷åñêèéãîðîäîâ.20052006./Ajtai, M. Approximate counting with uniform constant-depth circuits /M. Ajtai // Advances in computational complexity theory AmericanMathematical Society, 1993.
P. 120.1229.Alon, N. Simple constructions of almost k -wise independent randomvariables / N. Alon, O. Goldreich, J. Hastad, R. Peralta // RandomStructures and Algorithms. 1992. Vol. 3, no. 3. P. 289303.10. Arora, S. Computational Complexity: A Modern Approach / S. Arora,B. Barak Cambridge University Press, 2007. 579 p.11. Babai, L.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
