Автореферат (1103423), страница 4
Текст из файла (страница 4)
Çèìàíäà î êîëìîãîðîâñêèõ ýêñòðàêòîðàõ äëÿñëîæíîñòè áåç îãðàíè÷åíèé31,32, â äèññåðòàöèè ââîäÿòñÿ ïîíÿòèÿ ï¼ñò-ðûõ è ðàâíîìåðíî ï¼ñòðûõ òàáëèö. Çàòåì îíè ìîäèôèöèðóþòñÿ äëÿ ñëó÷àÿ ñëîæíîñòè ñ îãðàíè÷åíèåì íà ïàìÿòü, è ïðèìåíÿåòñÿ îïèñàííàÿ âãëàâå 4 òåõíèêà íàèâíîé äåðàíäîìèçàöèè. Òàêæå äîêàçûâàåòñÿ âàðèàíòòåîðåìû äëÿ ìàëûõ çíà÷åíèéåòñÿ íàs:â ýòîì ñëó÷àå îãðàíè÷åíèåµsçàìåíÿ-µs + poly(n).Çàêëþ÷åíèåÀ.Í. Êîëìîãîðîâ33ãîâîðèë î òð¼õ ïîäõîäàõ ê ïîíÿòèþêîëè÷å-ñòâî èíôîðìàöèè: êîìáèíàòîðíîì, âåðîÿòíîñòíîì è àëãîðèòìè÷åñêîì.Êàæäûé èç ýòèõ ïîäõîäîâ ïðåäñòàâëÿåò èíòåðåñ è äîâîëüíî ïîäðîáíîèçó÷åí, íî îñîáåííî èíòåðåñíû ñîîòíîøåíèÿ ìåæäó ðàçíûìè ïîäõîäàìè. äèññåðòàöèè óñòàíîâëåíû íîâûå ñâÿçè ìåæäó êîìáèíàòîðíûìè è àëãîðèòìè÷åñêèìè óòâåðæäåíèÿìè è ðàçðàáîòàí íîâûé ñïîñîá ðàñïðîñòðàíåíèÿ óòâåðæäåíèé îá îáû÷íîé êîëìîãîðîâñêîé ñëîæíîñòè íà ñëîæíîñòüñ îãðàíè÷åíèåì íà ðåñóðñû. Îäíàêî ìíîæåñòâî âîïðîñîâ îñòàþòñÿ íåðåø¼ííûìè.
Ïðåæäå âñåãî: êàêîâû ïðåäåëû ýòîãî ïîäõîäà? Êàêèå óòâåðæäåíèÿ î êîëìîãîðîâñêîé ñëîæíîñòè ìîæíî ïåðåëîæèòü äëÿ ñëîæíîñòèñ îãðàíè÷åíèåì íà ðåñóðñû ïîñðåäñòâîì êîìáèíàòîðíûõ óòâåðæäåíèé?Íàñêîëüêî óíèâåðñàëåí ìåòîäíàèâíîé31 M.äåðàíäîìèçàöèè? Ìîæíî ëèZimand. Extracting the Kolmogorov Complexity...Zimand. Impossibility of Independence Amplication...33 À.Í. Êîëìîãîðîâ.
Òðè ïîäõîäà...32 M.14äîêàçàòü êàêóþ-ëèáî îáùóþ òåîðåìó íà ýòîò ñ÷¼ò? Ýòè âîïðîñû ÿâëÿþòñÿ ïðåäìåòîì äàëüíåéøåãî èçó÷åíèÿ.Åù¼ îäíî âàæíîå íàïðàâëåíèå ðàçâèòèÿ ïîñòðîåíèå ÿâíûõ êîíñòðóêöèé èñïîëüçîâàííûõ â äèññåðòàöèè êîìáèíàòîðíûõ îáúåêòîâ. Íàïðèìåð, ïîñòðîåíèå ÿâíûõ ýêñòðàêòîðîâ ñ îïòèìàëüíûìè ïàðàìåòðàìèñòàëî áû ïðîðûâîì ñðàçó âî ìíîãèõ îáëàñòÿõ. Áûëî áû èíòåðåñíî ïîñòðîèòü ýêñòðàêòîð ñ îïòèìàëüíûìè ïàðàìåòðàìè, âû÷èñëèìûé íà ïîëèíîìèàëüíîé ïàìÿòè: òîãäà áû äëÿ ñîîòâåòñòâóþùåãî àíàëîãà òåîðåìûÌó÷íèêà íå íóæíî áûëî áû íàèâíîé äåðàíäîìèçàöèè.
Âîçìîæíî, íàîáîðîò, ìåòîäîì íàèâíîé äåðàíäîìèçàöèè ìîæíî ïîñòðîèòü òàêîé ýêñòðàêòîð. Ìîæíî ëè ïðè ïîìîùè êàêèõ-ëèáî ÿâíûõ ýêñòðàêòîðîâ äîêàçàòüòåîðåìó Ìó÷íèêà äëÿ îáû÷íîé ñëîæíîñòè ñ îãðàíè÷åíèåì íà ïàìÿòüâìåñòîCAM-ñëîæíîñòè?Âîçìîæíî, ýòî êàê-òî ñâÿçàíî ñî ñòàíäàðòíû-ìè òåîðåòèêî-ñëîæíîñòíûìè ïðåäïîëîæåíèåìè? Òàêæå îòëè÷íûì ðåçóëüòàòîì ñòàëî áû ïîñòðîåíèå ïîëèíîìèàëüíî âû÷èñëèìûõ ï¼ñòðûõòàáëèö: âîçìîæíî, ýòî ïîçâîëèëî áû äîêàçàòü ñóùåñòâîâàíèå êîëìîãîðîâñêèõ ýêñòðàêòîðîâ äëÿ ñëîæíîñòè ñ îãðàíè÷åíèåì íà âðåìÿ (õîòÿCAM-ñëîæíîñòè). Îòêðûòûì âîïðîñîì îñòà¼òñÿ ñïðàâåäëèâîñòüàíàëîãà òåîðåìû Ìó÷íèêà ñ äâóìÿ óñëîâèÿìè äëÿ CAM-ñëîæíîñòè.áû äëÿÌîæíî ñêàçàòü, ÷òî òåîðèÿ êîëìîãîðîâñêîé ñëîæíîñòè ñ îãðàíè÷åíèåì íà ðåñóðñû âñ¼ åù¼ íàõîäèòñÿ â ñòàäèè íàêîïëåíèÿ ôàêòîâ.
Äîâåñòèêîëè÷åñòâî èçâåñòíûõ ðåçóëüòàòîâ äî êðèòè÷åñêîé ìàññû è óëîæèòü èõâ ñòðîéíóþ òåîðèþ îñòà¼òñÿ çàäà÷åé áóäóùèõ èññëåäîâàíèé.ÁëàãîäàðíîñòèÏðåæäå âñåãî, àâòîð âûðàæàåò ãëóáîêóþ áëàãîäàðíîñòü ñâîåìó íàó÷íîìó ðóêîâîäèòåëþ Íèêîëàþ Êîíñòàíòèíîâè÷ó Âåðåùàãèíó çà ïîñòàíîâêó çàäà÷è î êîëìîãîðîâñêèõ ýêñòðàêòîðàõ, ïîñòîÿííîå âíèìàíèå èïîääåðæêó â ðàáîòå. Àâòîð áëàãîäàðèò ñâîèõ ñîàâòîðîâ è íàñòàâíèêîâÀíäðåÿ Ðîìàùåíêî è Àëåêñàíäðà Øåíÿ çà çíàêîìñòâî ñ òåìàòèêîé, ïîñòàíîâêó çàäà÷è î ïðèìåíåíèè ýêñòðàêòîðîâ ê çàäà÷å óñëîâíîãî êîäèðîâàíèÿ, ìíîãî÷èñëåííûå îáñóæäåíèÿ, ñîâåòû è êîíñòðóêòèâíóþ êðèòèêó ïî òåìàòèêå äèññåðòàöèè. Àâòîð âûðàæàåò îòäåëüíóþ áëàãîäàðíîñòüÀíäðåþ Àëüáåðòîâè÷ó Ìó÷íèêó (19582007) çà îáñóæäåíèå ðåçóëüòàòîâàâòîðà, ðàçâèâàþùèõ èäåè Àíäðåÿ Àëüáåðòîâè÷à.
Áåçâðåìåííàÿ êîí÷è-15íà Àíäðåÿ Àëüáåðòîâè÷à ñòàëà òÿæ¼ëîé óòðàòîé äëÿ ðîññèéñêîé íàóêè.Àâòîð áëàãîäàðèò ñâîèõ êîëëåã Âèêòîðà Áóëàòîâà, Ýäóàðäà Ãèðøà,Áðþíî Äþðàíà (Bruno Durand), Èëüþ Èðõèíà, Äìèòðèÿ Èöûêñîíà, Ðóñëàíà Èøêóâàòîâà, Þðèÿ Ïðèòûêèíà, Ìèõàèëà Ðàñêèíà è Àíäðåÿ Ðóìÿíöåâà çà îáñóæäåíèå îòäåëüíûõ ðàçäåëîâ ðàáîòû. Àâòîð áëàãîäàðèòÐîíåíà Øàëòèåëà (Ronen Shaltiel) çà ïîëåçíîå çàìå÷àíèå, ïîçâîëèâøååñóùåñòâåííî óïðîñòèòü äîêàçàòåëüñòâî îäíîãî èç óòâåðæäåíèé. Òàêæåàâòîð áëàãîäàðèò ìíîãî÷èñëåííûõ àíîíèìíûõ ðåöåíçåíòîâ, ñäåëàâøèõíåìàëî ïîëåçíûõ çàìå÷àíèé ïî òåêñòàì ñòàòåé àâòîðà, è ó÷àñòíèêîâ ñåìèíàðîâ â ÌÃÓ è ÌÔÒÈ çà âíèìàíèå è èíòåðåñ ê äîêëàäàì àâòîðà.Àâòîð áëàãîäàðèò îðãêîìèòåò Òóðíèðà Ãîðîäîâ è ëè÷íî Ñåðãåÿ Äîðè÷åíêî çà âêëþ÷åíèå â ñîñòàâ âàðèàíòà îñåííåãî òóðà 2005 ãîäà çàäà÷è,âîçíèêøåé â õîäå ðàáîòû íàä ðåçóëüòàòàìè äèññåðòàöèè.Íàêîíåö, àâòîð ãëóáîêî ïðèçíàòåëåí ñâîåé ñåìüå çà ïîñòîÿííóþ ïîääåðæêó.Ðàáîòû àâòîðà ïî òåìå äèññåðòàöèè1.Musatov,D.V.OnExtractingSpace-BoundedKolmogorovComplexity / D.V.
Musatov. // Theory of Computing Systems. 2014. DOI 10.1007/s00224-014-9563-7.2.Musatov,D.V.Space-BoundedKolmogorovExtractors/D.V. Musatov // Proceedings of the 7th Computer Science Symposiumin Russia. 2012. LNCS, Vol. 7353. P. 266277.3.Musatov, D.V. Improving the Space-Bounded Version of Muchnik'sConditionalComplexityTheoremviaNaiveDerandomization/D.V. Musatov // Theory of Computing Systems. 2014. Vol.
55,no. 2. P. 299312.4.Musatov, D.V. Improving the Space-Bounded Version of Muchnik'sConditionalComplexityTheoremviaNaiveDerandomization/D.V. Musatov // Proceedings of the 6th Computer Science Symposiumin Russia. 2011. LNCS, Vol. 6651. P. 6476.165.Musatov,D.V. Variations on Muchnik's Conditional ComplexityTheorem / D.V. Musatov, A.E.
Romashchenko, A. Shen // Theory ofComputing Systems. 2011. Vol. 49, no. 2. P. 227245.Ñîèñêàòåëþ ïðèíàäëåæàò äîêàçàòåëüñòâà âñåõ òåîðåì èç ðàçäåëà 3.6.Musatov,D.V. Variations on Muchnik's Conditional ComplexityTheorem / D.V. Musatov, A.E. Romashchenko, A. Shen // Proceedingsof the 4th Computer Science Symposium in Russia. 2009. LNCS,Vol. 5675. P. 250262.Ñîèñêàòåëþ ïðèíàäëåæàò äîêàçàòåëüñòâà âñåõ òåîðåì èç ðàçäåëà 3.7.Ìóñàòîâ Ä.Â.
Óïðîù¼ííîå äîêàçàòåëüñòâî òåîðåìû Ìó÷íèêà îáóñëîâíîé êîëìîãîðîâñêîé ñëîæíîñòè ñ îãðàíè÷åíèåì íà ïàìÿòü /Ä.Â. Ìóñàòîâ // Òðóäû 55-îé íàó÷íîé êîíôåðåíöèè ÌÔÒÈ. Ì.ÄîëãîïðóäíûéÆóêîâñêèé: ÌÔÒÈ, 2012. Ñ. 3031.17.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
