Автореферат (1103423), страница 2
Текст из файла (страница 2)
Ðîìàùåíêîî ñèììåòðèè èíôîðìà-öèè, à òàêæå ðàáîòó Ã. Áþðìàíà, Ò. Ëè è Ä. âàí Ìåëêåáååêà î ñæàòèè19ÿçûêîâ.Äëÿ ñëîæíîñòè ñ îãðàíè÷åíèåì íà ðåñóðñû ñòàíîâèòñÿ âàæíàìîäåëü âû÷èñëåíèé: èñïîëüçîâàíèå íåäåòåðìèíèçìà è/èëè ñëó÷àéíîñòèìîæåò ñóùåñòâåííî óìåíüøèòü ñëîæíîñòü.  ÷àñòíîñòè, èçó÷àþòCAM-ñëîæíîñòü äëÿ íåäåòåðìèíèðîâàííûõ âåðîÿòíîñòíûõ âû÷èñëåíèé. Ýòà20ìîäåëü áûëà ââåäåíà Ë. Áàáàåìè ïîëó÷èëà ìåòàôîðè÷åñêîå íàçâàíèåèãð ÀðòóðàÌåðëèíà. Ìåòàôîðà îáúÿñíÿåòñÿ òàê: âû÷èñëåíèÿ ïðîâîäèòÀðòóð, áåñåäóþùèé ñ ìàãîì Ìåðëèíîì.
Àðòóð ìîæåò áðîñàòü ìîíåòêó(ò.å. ïîëó÷àòü ñëó÷àéíûå áèòû) è ñîâåðøàòü ïîëèíîìèàëüíûå âû÷èñëåíèÿ. Ìåðëèí ìîæåò âû÷èñëÿòü ëþáûå ôóíêöèè (äàæå íå âû÷èñëèìûåàëãîðèòìè÷åñêè) è ìãíîâåííî óçíà¼ò ñëó÷àéíûå áèòû Àðòóðà. Âçàèìî13 J.M. Hitchcock, A. Pavan, N.V. Vinodchandran.
Kolmogorov Complexity in Randomness Extraction// ACM Transactions on Computation Theory. 2011. V. 3. 1. P. 1:11:15.14 L. Fortnow, J. Hitchcock, A. Pavan, N.V. Vinodchandran, F. Wang. Extracting KolmogorovComplexity with Applications to Dimension Zero-One Laws // Information and Computation. 2011. V. 209. 4. P. 627636.15 M. Zimand.
Two Sources are Better than One for Increasing the Kolmogorov Complexity of InniteSequences // Proceedings of the 3rd Computer Science Symposium in Russia. 2008. LNCS,V. 5010. P. 326338.16 M. Zimand. Extracting the Kolmogorov Complexity of Strings and Sequences from Sources withLimited Independence // Proceedings the 26th Symposium on Theoretical Aspects of ComputerScience.
2009. P. 697708.17 M. Zimand. Impossibility of Independence Amplication in Kolmogorov Complexity Theory //Proceedings of the 35th International Symposium on Mathematical Foundations of Computer Science. 2010. LNCS, V. 6281. P. 701712.18 T. Lee, A. Romashchenko. Resource-Bounded Symmetry of Information Revisited // TheoreticalComputer Science. 2005. V. 345. 23. P. 386405.19 H. Buhrman, T. Lee, D. van Melkebeek.
Language Compression and Pseudorandom Generators //Computational Complexity. 2005. V. 14. P. 247274.20 L. Babai. Trading Group Theory for Randomness // Proceedings of the 17th annual ACMsymposium on Theory of computing. 1985. P. 421429.4äåéñòâèå óñòðîåíî òàê: ñíà÷àëà Àðòóð êèäàåò ìîíåòêó íåîáõîäèìîå ÷èñëî ðàç, çàòåì Ìåðëèí óçíà¼ò ðåçóëüòàòû è ïîñûëàåò íåêîòîðîå ñîîáùåíèå, çàòåì Àðòóð ïðîâîäèò ïîëèíîìèàëüíûå âû÷èñëåíèÿ è âûäà¼ò îòâåò.Îòâåòîì ìîæåò áûòü ëèáî äâîè÷íîå ñëîâî, ëèáî ñèìâîë îøèáêè⊥. Ñëîâîx íàçûâàåòñÿ ðåçóëüòàòîì ðàáîòû ïðîãðàììû, åñëè ñ âåðîÿòíîñòüþ õîòÿáûx23 îäíîâðåìåííî âûïîëíåíû äâà óñëîâèÿ: âî-ïåðâûõ, Àðòóð âûäàñòïðè íåêîòîðûõ ñîîáùåíèÿõ Ìåðëèíà; âî-âòîðûõ, ïðè ëþáûõ äðóãèõñîîáùåíèÿõ Ìåðëèíà Àðòóð âûäàñò ëèáî òî æåx,ëèáî⊥.Âàæíûì òåõíè÷åñêèì èíñòðóìåíòîì, èñïîëüçóåìûì â äèññåðòàöèè,ÿâëÿåòñÿ ãåíåðàòîð ïñåâäî-ñëó÷àéíûõ ÷èñåë ÍèñàíàÂèãäåðñîíà.Ýòîò ãåíåðàòîðîáìàíûâàåò21,22âñå ñõåìû èç ôóíêöèîíàëüíûõ ýëåìåí-òîâ ïîëèíîìèàëüíîãî ðàçìåðà è êîíñòàíòíîé ãëóáèíû, ò.å.
òàêèå ñõåìûâûäàþò àñèìïòîòè÷åñêè îäèíàêîâûé ðåçóëüòàò íà ñëó÷àéíîì ñëîâå è íàñëó÷àéíîì çíà÷åíèè ãåíåðàòîðà.  äèññåðòàöèè ãåíåðàòîð èñïîëüçóåòñÿíàèâíûìîáðàçîì, ñðîäíè ðàáîòå À.Å. Ðîìàùåíêî:23âìåñòî ñëó÷àéíî-ãî êîìáèíàòîðíîãî îáúåêòà ðàññìàòðèâàåòñÿ ïñåâäîñëó÷àéíûé, ÷òî ñóùåñòâåííî óìåíüøàåò îáëàñòü ïåðåáîðà è ïîçâîëÿåò äîêàçàòü òåîðåìûäëÿ îãðàíè÷åííûõ ðåñóðñîâ.Öåëè è çàäà÷è ðàáîòûÎñíîâíîé çàäà÷åé ðàáîòû ÿâëÿåòñÿ èçó÷åíèå ñâÿçåé ìåæäó êîìáèíàòîðíûìè êîíñòðóêöèÿìè è óòâåðæäåíèÿìè î êîëìîãîðîâñêîé ñëîæíîñòèè èñïîëüçîâàíèå ýòèõ ñâÿçåé äëÿ ðàñïðîñòðàíåíèÿ èçâåñòíûõ òåîðåì îêîëìîãîðîâñêîé ñëîæíîñòè íà ñëîæíîñòü ñ îãðàíè÷åíèåì íà âû÷èñëèòåëüíûå ðåñóðñû.Îñíîâíûå ðåçóëüòàòûÐàáîòà ñîäåðæèò ÷åòûðå îñíîâíûõ ðåçóëüòàòà. Ðåçóëüòàòû ÿâëÿþòñÿíîâûìè, ïîëó÷åíû àâòîðîì ñàìîñòîÿòåëüíî è ñîñòîÿò â ñëåäóþùåì.Âî-ïåðâûõ, óñòàíîâëåíà ñâÿçü òåîðåìû Ìó÷íèêà îá óñëîâíîì êîäèðîâàíèè è òåîðèè ýêñòðàêòîðîâ. Ñ èñïîëüçîâàíèåì ëåììû Áþðìàíà21 N.Nisan.
Pseudorandom Bits for Constant Depth Circuits // Combinatorica. 1991. V. 11. 1.P. 6370.22 N. Nisan, A. Wigderson. Hardness vs. Randomness. // Journal of Computer and System Sciences. 1994. V. 49. P. 149167.23 A.E. Romashchenko. Pseudo-Random Graphs and Bit Probe Schemes with One-Sided Error //Theory of Computing Systems. 2014.
V. 55. 2. P. 313329.5ÔîðòíîóËàïëàíò24äîêàçàíî, ÷òî êîìáèíàòîðíîå ñâîéñòâî ýêñòðàêòîðàïîçâîëÿåò äîêàçàòü òåîðåìó Ìó÷íèêà îá óñëîâíîì êîäèðîâàíèè. Òàêæåïîêàçàíî, ÷òî àíàëîãè÷íîé òåõíèêîé ìîæíî ïîëó÷èòü òåîðåìó Ìó÷íèêàäëÿ íåñêîëüêèõ óñëîâèé (âïëîòü äî ïîëèíîìèàëüíîãî ÷èñëà).
Äëÿ ýòîãîèñïîëüçóþòñÿ ïðåôèêñíûå ýêñòðàêòîðû.Âî-âòîðûõ, äîêàçàíû àíàëîãè òåîðåìû Ìó÷íèêà äëÿ ñëîæíîñòè ñîãðàíè÷åíèåì íà ïàìÿòü. Ïðèìåíÿþòñÿ äâå òåõíèêè: èñïîëüçîâàíèå ÿâíûõ ýêñòðàêòîðîâ è èñïîëüçîâàíèå ïñåâäîñëó÷àéíûõ ãåíåðàòîðîâ. Êîìáèíàöèåé äâóõ ïîäõîäîâ ïîëó÷åí àíàëîã òåîðåìû äëÿ ëîãàðèôìè÷åñêîéòî÷íîñòè ïðè ëþáîì îãðàíè÷åíèè íà ïàìÿòü. Òàêæå äîêàçàíû àíàëîãèòåîðåìû Ìó÷íèêà äëÿ íåñêîëüêèõ èñòî÷íèêîâ.
Ïðèìåíåíèå òåõíèêè ãåíåðàòîðîâ ïñåâäîñëó÷àéíûõ ÷èñåë ïîçâîëèëî äîêàçàòü òåîðåìó íå òîëüêî äëÿ ïîëèíîìèàëüíîãî, íî è äëÿ ýêñïîíåíöèàëüíîãî ÷èñëà óñëîâèé ïðèïîëèíîìèàëüíîì îãðàíè÷åíèè íà ïàìÿòü.Â-òðåòüèõ, äîêàçàí àíàëîã òåîðåìû Ìó÷íèêà äëÿCAM-ñëîæíîñòèñ îãðàíè÷åíèåì íà âðåìÿ. Çäåñü êîäèðîâàíèå îñóùåñòâëÿåòñÿ îáû÷íûìïîëèíîìèàëüíûì àëãîðèòìîì, à äåêîäèðîâàíèå ïðîèñõîäèò ïðè ïîìîùèàëãîðèòìà èç êëàññàAM.Â-÷åòâ¼ðòûõ, îïðåäåëåíû è ïîñòðîåíû îáû÷íûå è óñèëåííûå êîëìîãîðîâñêèå ýêñòðàêòîðû ñ îãðàíè÷åíèåì íà ïàìÿòü.
Êîíñòðóêöèè Çèìàíäà,äîêàçûâàþùèå ñóùåñòâîâàíèå òàêèõ ýêñòðàêòîðîâ ñ îïòèìàëüíûìè ïàðàìåòðàìè, óïðîùåíû è ïåðåëîæåíû äëÿ íîâûõ îïðåäåëåíèé. Èñïîëüçîâàíà ðàçðàáîòàííàÿ ïðè äîêàçàòåëüñòâå àíàëîãîâ òåîðåìû Ìó÷íèêàòåõíèêà ïñåâäîñëó÷àéíûõ ãåíåðàòîðîâ.Îñíîâíûå ìåòîäû èññëåäîâàíèÿ ðàáîòå èñïîëüçîâàíû êîìáèíàòîðíûå ìåòîäû äîêàçàòåëüñòâà óòâåðæäåíèé î êîëìîãîðîâñêîé ñëîæíîñòè. Èñïîëüçîâàíû òàêèå êîìáèíàòîðíûå êîíñòðóêöèè, êàê ýêñòðàêòîðû (â ÷àñòíîñòè, ýêñòðàêòîð Òðåâèñàíà)è ãåíåðàòîðû ïñåâäîñëó÷àéíûõ ÷èñåë.24 H.Buhrman, L. Fortnow, S. Laplante. Resource bounded Kolmogorov complexity revisited // SIAMJournal on Computing. 2002. V. 31.
3. P. 887905.6Òåîðåòè÷åñêàÿ è ïðàêòè÷åñêàÿ öåííîñòüÐàáîòà èìååò òåîðåòè÷åñêèé õàðàêòåð. Ïîëó÷åííûå ðåçóëüòàòû ïðåäñòàâëÿþò èíòåðåñ äëÿ ñïåöèàëèñòîâ ïî òåîðèè êîëìîãîðîâñêîé ñëîæíîñòè. Ìåòîäû, ðàçðàáîòàííûå àâòîðîì â äèññåðòàöèîííîé ðàáîòå, áûëèèñïîëüçîâàíû25,26è ìîãóò áûòü èñïîëüçîâàíû â äàëüíåéøåì äëÿ äîêà-çàòåëüñòâà äðóãèõ ðåçóëüòàòîâ î êîëìîãîðîâñêîé ñëîæíîñòè ñ îãðàíè÷åíèåì íà âû÷èñëèòåëüíûå ðåñóðñû.Àïðîáàöèÿ ðàáîòûÎñíîâíûå ðåçóëüòàòû, ïîëó÷åííûå â ðàáîòå, áûëè èçëîæåíû íà ìåæäóíàðîäíûõ êîíôåðåíöèÿõ Computer Science in Russia â Íîâîñèáèðñêå(1823 àâãóñòà 2009 ã.), â Ñàíêò-Ïåòåðáóðãå (1418 èþíÿ 2011 ã.) è âÍèæíåì Íîâãîðîäå (37 èþëÿ 2012 ã.)Êðîìå òîãî, ðåçóëüòàòû áûëè äîëîæåíû íà ñëåäóþùèõ ìåæäóíàðîäíûõ è âñåðîññèéñêèõ íàó÷íûõ êîíôåðåíöèÿõ è ñåìèíàðàõ:•8-àÿ ìåæäóíàðîäíàÿ êîíôåðåíöèÿ ïî âû÷èñëèìîñòè, ñëîæíîñòè èñëó÷àéíîñòè (CCR), Ìîñêâà, 2123 ñåíòÿáðÿ 2013 ã.•56-ÿ íàó÷íàÿ êîíôåðåíöèÿ ÌÔÒÈ, ñåêöèÿ äèñêðåòíîé ìàòåìàòèêè,Äîëãîïðóäíûé, 2530 íîÿáðÿ 2013 ã.•55-ÿ íàó÷íàÿ êîíôåðåíöèÿ ÌÔÒÈ, ñåêöèÿ äèñêðåòíîé ìàòåìàòèêè,Äîëãîïðóäíûé, 1925 íîÿáðÿ 2012 ã.•Êîëìîãîðîâñêèé ñåìèíàð ïî ñëîæíîñòè âû÷èñëåíèé è ñëîæíîñòè îïðåäåëåíèé, ìåõàíèêî-ìàòåìàòè÷åñêèé ôàêóëüòåò ÌÃÓ èì.Ì.Â.Ëîìîíîñîâà, 20062012 ãã.•Êàôåäðàëüíûé ñåìèíàð êàôåäðû äèñêðåòíîé ìàòåìàòèêè ôàêóëüòåòà èííîâàöèé è âûñîêèõ òåõíîëîãèé ÌÔÒÈ(ÃÓ), 20092013 ãã.•Ñåìèíàð ïî äèñêðåòíîé ìàòåìàòèêå Ïåòåðáóðãñêîãî îòäåëåíèÿ ìàòåìàòè÷åñêîãî èíñòèòóòà èì.
Â.À.Ñòåêëîâà ÐÀÍ, 2012 ã.•Ñåìèíàð Äàâèäà Ãàìàðíèêà â Ìàññà÷óñåòñêîì Òåõíîëîãè÷åñêîì èíñòèòóòå (ÑØÀ), 2012 ã.25 M.Zimand. Symmetry of Information and Bounds on Nonuniform Randomness Extraction viaKolmogorov Extractors // Proceedings of the 26th IEEE Conference in Computational Complexity. 2011. P.
148156.26 M. Zimand. On the Optimal Compression of Sets in PSPACE // Proceedings of the 18thInternational Symposium on Fundamentals of Computation Theory. 2011. P. 6577.7ÏóáëèêàöèèÎñíîâíûå ðåçóëüòàòû äèññåðòàöèè áûëè îïóáëèêîâàíû â ñáîðíèêàõ òðóäîâ ìåæäóíàðîäíûõ êîíôåðåíöèé Computer Science in Russia[2; 4; 6] (ñåðèÿ Lecture Notes in Computer Science, âõîäèò â ñèñòåìó Scopus) è ñïåöèàëüíûõ âûïóñêàõ æóðíàëà Theory of ComputingSystems [1; 3; 5] (âõîäèò â ñèñòåìó Web of Science).  ñîâìåñòíûõ ñòàòüÿõ [5] è [6] ñîèñêàòåëþ ïðèíàäëåæàò ìåòîä äîêàçàòåëüñòâà òåîðåìûÌó÷íèêà ïðè ïîìîùè ýêñòðàêòîðîâ è òåîðåìà äëÿCAM-ñëîæíîñòè.Óïðîù¼ííîå äîêàçàòåëüñòâî îäíîé èç òåîðåì áûëî îïóáëèêîâàíî â ìàòåðèàëàõ 55-îé íàó÷íîé êîíôåðåíöèè ÌÔÒÈ [7].Ñòðóêòóðà äèññåðòàöèèÄèññåðòàöèÿ ñîñòîèò èç ââåäåíèÿ, îáçîðà îñíîâíûõ ïîíÿòèé, ÷åòûð¼õãëàâ ñ èçëîæåíèåì îñíîâíûõ ðåçóëüòàòîâ ðàáîòû, çàêëþ÷åíèÿ è ñïèñêàëèòåðàòóðû èç 65 íàèìåíîâàíèé.
Äèññåðòàöèÿ ñîäåðæèò 18 èëëþñòðàöèéè 6 àëãîðèòìîâ, çàïèñàííûõ íà ïñåâäîêîäå. Îáùèé îáú¼ì äèññåðòàöèèñîñòàâëÿåò 128 ñòðàíèö, âêëþ÷àÿ 118 ñòðàíèö îñíîâíîãî òåêñòà.Îñíîâíîå ñîäåðæàíèå ðàáîòûÃëàâà 1 ÿâëÿåòñÿ ââåäåíèåì äèññåðòàöèè. Îíà ñîäåðæèò îïèñàíèå àê-òóàëüíîñòè òåìû, öåëè ðàáîòû, ñïèñîê îñíîâíûõ ðåçóëüòàòîâ, ñâåäåíèèîá àïðîáàöèè ðàáîòû è ñïèñîê èñïîëüçóåìûõ îáîçíà÷åíèé. ãëàâå 2 ïðèâåä¼í îáçîð îñíîâíûõ ïîíÿòèé è ðåçóëüòàòîâ, èñïîëüçóåìûõ â äèññåðòàöèè. Îñâåùåíû òàêèå îáëàñòè, êàê êîëìîãîðîâñêàÿñëîæíîñòü, ýêñòðàêòîðû, êîëìîãîðîâñêèå ýêñòðàêòîðû, ñõåìû èç ôóíêöèîíàëüíûõ ýëåìåíòîâ, ãåíåðàòîðû ïñåâäîñëó÷àéíûõ ÷èñåë. Òàêæå ïðèâåäåíû ôîðìóëèðîâêè âàæíûõ òåõíè÷åñêèõ ðåçóëüòàòîâ: âû÷èñëèòåëüíîé XOR-ëåììû è íåðàâåíñòâà ×åðíîâàÕ¼ôôäèíãà.
 àâòîðåôåðàòåïðèâåäåíû òîëüêî îïðåäåëåíèÿ, èñïîëüçóåìûå â ôîðìóëèðîâêàõ ñîîòâåòñòâóþùèõ òåîðåì. ãëàâå 3 èçëàãàåòñÿ íîâîå äîêàçàòåëüñòâî òåîðåìû Ìó÷íèêà îáóñëîâíîì êîäèðîâàíèè ïðè ïîìîùè ýêñòðàêòîðîâ.Îïðåäåëåíèå 1. Ïóñòüàðãóìåíòîâ.U óíèâåðñàëüíàÿ âû÷èñëèìàÿ ôóíêöèÿ äâóõÓñëîâíîé êîëìîãîðîâñêîé ñëîæíîñòüþ8ñëîâàxîòíîñè-òåëüíî ñëîâàU (p, y) = x.yíàçûâàåòñÿ äëèíà êðàò÷àéøåãî ñëîâàðîâñêîé ñëîæíîñòüþñëîâàòàêîãî ÷òîÁåçóñëîâíîé êîëìîãî-C(x|y).x íàçûâàåòñÿ C(x) = C(x|ε),Ýòî ÷èñëî áóäåì îáîçíà÷àòüp,ãäåε ïóñòîåñëîâî.Íåôîðìàëüíî òåîðåìà Ìó÷íèêà ãëàñèò ñëåäóþùåå: ñðåäè âñåõ ïðî-b â a è èìåþùèõ áëèçêóþ ê ìèíèìàëüíîé äëèíó,íàéä¼òñÿ ïðîãðàììà p, ïðîñòàÿ îòíîñèòåëüíî a.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
