Першопрохідці теоретичної інформатики

Премія Абеля — одна з найбільш престижних нагород у галузі математики, заснована Норвезькою академією наук у 2002 році. Названа на честь геніального норвезького математика Нільса Хенріка Абеля (1802-1829), вона щорічно присуджується одному або кільком вченим за видатний внесок у розвиток дисципліни. Про лауреатів премії 2021 року розповідає докт. фіз.-мат. наук, член-корр. РАН, гл. сотр. МІАН, професор факультету математики Чиказького університету (США) Олександр Разборов.

Олександр Разборов. Фото: Jean Lachat

Минулого тижня були оголошені лауреати Абелівської премії за 2021 рік. Ними стали Ласло Ловас (Lászl^ Lovász, Математичний інститут ім. Реньї Академії наук Угорщини) і Аві Вігдерсон (Avi Wigderson, Інститут перспективних досліджень (IAS), Прінстон). Відповідно до прес-релізу [1], премія була присуджена за «основоположний внесок у теоретичну інформатику і дискретну математику і провідну роль лауреатів у становлення цих дисциплін як центральних областей сучасної математики».

Формулювання Абелівського комітету в даному випадку настільки точне і карбоване, що додати до нього що-небудь, по суті, важко. Тому, як і інші автори (див. наприклад, [2]), я в основному спробую проілюструвати думки, що містяться в ній (можливо, в злегка завуальованій формі).

Дискретна математика, як випливає вже з назви, займається вивченням властивостей кінцевих, дискретних об’єктів. Досить значна її частина, традиційно звана комбінаторикою, мотивована структурами, що виникають в «чистій» математиці. Наприклад, фундаментальне для топології поняття симпліціального комплексу з комбінаторної точки зору не що інше, як замкнене сімейство кінцевих безліч, відповідних граням комплексу. Комбінаторна абстракція в багатьох випадках призводить до чудових наслідків, і така «корисна» (тобто, як би це дивно не звучало, прикладна по відношенню до фундаментальної математики) комбінаторика завжди користувалася заслуженою повагою математичної спільноти.

Однак, у цій замітці швидше цікавить точка зору на дискретну математику як на самостійну дисципліну, що виходить з того, що вивчення кінцевих структур, таких як, наприклад, графи або безлічі, в рамках однієї зв’язної теорії цікаво саме по собі, незалежно від їх негайних додатків. І тоді картина взаємин з «чистою» математикою негайно стає набагато складнішою.

Ласло Ловас

Погляд, описаний у попередньому абзаці, протягом довгого часу асоціювався з тим, що називалося «угорською математикою», і найбільш активним його прихильником і пропагандистом був, звичайно, Пол Ердеш (Pál Erd^ s). Ласло Ловас народився в Будапешті (Угорщина) 1948 року і виховувався в цій математичній культурі. Зокрема, він познайомився з Ердешем в досить ранньому віці, і це мало дуже великий вплив на його подальшу кар’єру і світогляд. У деякому відношенні Л. Ловаса можна вважати прямим спадкоємцем П. Ердеша, який продовжив і в певному сенсі завершив справу його життя; про це йтиметься нижче.

Становлення теоретичної інформатики

Теоретична інформатика, або, як іноді прийнято говорити, комп’ютерні науки, виникла як самостійна дисципліна приблизно в 1970-ті роки, коли були закладені основи того, що зазвичай називають «теорією складності обчислень». У цій дисципліні, грубо кажучи, вивчаються питання існування або, частіше, неіснування алгоритмів із поставленими обмеженнями на їх ефективність.

Незважаючи на свою назву, теоретична інформатика — наука суворо математична, і всі її досягнення формулюються у вигляді суворих визначень, теорем і лем, так само як і в інших галузях математики. Тим не менш, поряд з внутрішньою логікою розвитку, теоретична інформатика багато в чому також керується практичними додатками, іноді цілком конкретними. Цілком очевидно, що, як і до будь-якої іншої «напівприкладної» дисципліни, ставлення до неї «чистих» математиків залишалося протягом довгого часу, м’яко кажучи, настороженим.

Аві Вігдерсон

Аві Вігдерсон народився 1956 року в Хайфі (Ізраїль), і його студентські роки припали на період становлення теоретичної інформатики, і зокрема теорії складності обчислень як окремої, самостійної дисципліни. Під час навчання в аспірантурі Прінстона великий вплив на Аві зробив його науковий керівник Дік Ліптон (Richard Jay Lipton), один з батьків-засновників теорії складності. Так само як і у випадку з Ловасом, теоретична інформатика стала справою його життя.

Одна з головних заслуг обох лауреатів (про їх конкретні досягнення я поговорю нижче), з моєї точки зору, полягає в тому, що процес дорослішання і становлення обох дисциплін протягом десятиліть багато в чому визначався їх науковими роботами, а також багатосторонньою педагогічною та популяризаторською діяльністю.

При цьому виявилося, що в силу природних причин — більшість об’єктів, якими оперують комп’ютери, дискретні — теоретична інформатика є вдячним споживачем результатів, ідей і концепцій дискретної математики, багато з яких не були затребувані в «чистій» математиці. У свою чергу, потреби теоретичної інформатики призвели до створення абсолютно нових областей дискретної математики, так що це, на мою думку, один з найбільш вдалих симбіозів в історії науки. Величезна заслуга в цьому «перенесенні ідей» з однієї області в іншу також належить лауреатам премії Абеля цього року.

Змінилися в кращу сторону і відносини з «чистою» математикою і математиками. Наприклад, Ласло Ловас (до слова, іноземний член РАН) був президентом Міжнародного математичного союзу протягом чотирьох років (2007-2010), а позиція Аві Вігдерсона в принстонському IAS відноситься до Школи математики (The School of Mathematics); на початку описуваного шляху те й інше було б немислимо. Це відбувалося більш-менш природним чином, шляхом накопичення в обох дисциплінах завдань, ідей і постановок, найтіснішим чином пов’язаних з багатьма областями абстрактної математики і в багатьох випадках впливають на її власний розвиток. І в цьому відношенні Ласло і Аві ставляться до безумовних лідерів.

Переходячи до більш конкретних речей, обмовлюся, що навіть короткий переказ найбільш видатних досягнень обох лауреатів у замітці такого розміру неможливий. Я наведу в якості прикладів по одному загальному напрямку і по одному конкретному результату; вибір матеріалу повністю суб’єктивний.

Від дискретності до безперервності

Ми зазначали вище, що характерною рисою дискретної математики є її підвищений інтерес до кінцевих (на відміну від безперервних) об’єктів. Ласло Ловас — один із засновників і, мабуть, головна дійова особа дуже важливого проекту, в основу якого закладена прямо протилежна посилка. Виявляється, що дуже великі графи та інші комбінаторні об’єкти можна розумним чином розглядати як наближення до деяких природних безперервних структур геометричної або алгебраїчної природи приблизно в тому ж сенсі (аналогія Ловаса), в якому десяткові дроби можна розглядати як наближення ірраціональних чисел. Виходить красива і струнка теорія, яка виявляється дивним чином пов’язаною не тільки з комбінаторикою, що природно, але і з зовсім різними областями математики і навіть фізики: алгеброю, аналізом, теорією міри, статистичною механікою, ергодичною теорією тощо.

Ласло Ловасу належить чудово і зрозуміло написана монографія «Великі мережі і межі графів» (Large Networks and Graph Limits), яка швидко стала класичним текстом у цій області; я рекомендую її всім зацікавленим читачам.

Теорія псевдовипадковості

Якщо називати якусь одну тему, яка найбільше асоціюється з ім’ям Аві Вігдерсона, в цій ролі, швидше за все, виступить теорія псевдопромінюваності. Почну з вихідної мотивації. Багато найважливіших алгоритмів за своєю природою ймовірні, тобто використовують у своїй роботі датчики випадкових чисел. Однак абсолютна випадковість зустрічається рідко, і на практиці майже завжди використовуються так звані генератори псевдопромінювальних чисел, які видають за випадкові біти, згенеровані детермінованою процедурою, в надії, що алгоритм такої підміни «не помітить».

Теорія псевдопромінюваності, грубо кажучи, намагається підвести під цю надію теоретичну базу шляхом побудови генераторів з різною архітектурою і параметрами, для яких вдається довести математично, що вони мають необхідні властивості. При цьому досить швидко з’ясовується, що ці об’єкти і концепції мають і інші, абсолютно незалежні програми в теорії складності обчислень, а також що відповідні конструкції пов’язані з абсолютно класичними областями математики, такими як, наприклад, алгебраїчна геометрія. Аві Вігдерсон — безумовний і загальновизнаний лідер у цій галузі; йому, зокрема, належать як найбільш важливі конструкції (генератор Нісана — Вігдерсона), так і їх чудові слідства в теорії складності (теорема Імпальяццо — Вігдерсона).

Гіпотеза Кнезера

Мій улюблений конкретний результат Ласло Ловаса — це його доказ гіпотези Кнезера. Граф Кнезера — це дуже природний кінцевий граф, що виникає в алгебраїчній комбінаториці, і завдання полягає в тому, щоб обчислити його хроматичне число — тобто найменше число кольорів, в які його вершини можна пофарбувати так, що сполучені ребром вершини завжди пофарбовані в різні кольори.

Граф Кнезера. Зображення з Вікіпедії

Імовірно, оптимальну розмальовку побудувати легко; проблема полягає в тому, щоб довести, що поліпшити її не можна. Ця проблема, яка не піддавалася жодним комбінаторним зусиллям майже 25 років, була вирішена в елегантній статті Ловаса 1978 року шляхом занурення всієї суто дискретної картинки в багатовимірну сферу і застосування теореми Борсука — Улама — одного з наріжних результатів речової топології. З цього доказу зросла ціла дисципліна, звана сьогодні топологічною комбінаторикою, методами якої вдалося вирішити цілий ряд інших неприступних завдань.

Система резолюцій

Теорія складності доказів вивчає наявність ефективних доказів різних природничих тверджень, таких як, наприклад, математичні теореми, твердження про неіснування розмальовки даного графа в дане число кольорів або про те, що даний код не містить помилок. Найбільш важливою системою доказів є так звана система резолюцій, в тому числі і тому, що засновані на ній алгоритми мають широке практичне застосування.

Методи дослідження системи резолюцій були відомі досить давно, але до роботи Е.Бен-Сассона (Eli Ben-Sasson) і А. Вігдерсона 2001 року вони в кращому випадку носили приватний характер. У цій роботі був запропонований дивовижно простий загальний метод аналізу таких доказів, заснований на залученні ще одного заходу складності, званої шириною. У теорії складності доказів ця робота стала хрестоматійною і викликала до життя цілу низку нових ідей і концепцій.

1 The Abel Prize Laureates 2021.

2 Kevin Hartnett. Pioneers Linking Math and Computer Science Win the Abel Prize // Quanta Magazine. 17.03.2021.