Математик, по мнению коллег, выступавших в роли учеников на мастер-классе, обязательно выльет воду и сведет задачу к предыдущей. Михаил Случ кивает и задает другой вопрос: «А кто из персонажей байки действует более эффективно?» Коллеги уверены, что физик. «Или математик? - уточняет Михаил Случ. - К этому вопросу вернемся. В ближайшие двадцать минут мы будем решать задачи, сравнивать пути решений, а среди решений - важный момент - мы будем искать наиболее эффективное. Двигаясь от простого к сложному, попробуем уточнить сами понятия простого и сложного».
На экране возникают пятьдесят мужских портретов. Один из этих портретов принадлежит известному математику и академику Андрею Николаевичу Колмогорову, его и предстоит найти присутствующим коллегам-ученикам. Для наглядности фотография Колмогорова продублирована рядом с массивом. Участники практически сразу справляются с решением задачи.
Получив ответ, Михаил Случ усложняет задачу, увеличив объем данных: теперь на экране вместо пятидесяти представлено около двухсот фотографий. «Как изменится время решения?» - интересуется математик. «В четыре раза увеличится», - отвечает кто-то из коллег.
Михаил Случ еще раз меняет условия задачи: теперь нужно найти среди пятидесяти фотографий два одинаковых лица. Математик просит даже не только и не столько найти ответ, а, скорее, определить, сложнее это задание, чем предыдущее, или же проще. Участники делятся мнениями, их ответы разнятся: «Примерно одинаково», «Нет, сложнее». Михаил Случ не поясняет, какой из ответов правильный. «Для меня сейчас важно, что сами эти разговоры вокруг простого и сложного не такие простые, - поясняет математик. - Это тема моего мастер-класса «Введение в теорию сложности». Мы будем искать количественные характеристики того, что такое «просто» и что такое «сложно».
По ходу мастер-класса участникам необходимо было найти путь решения каждой из разобранных задач - алгоритм, разобраться, из какого числа операций этот алгоритм состоит, сколько времени занимает конкретное решение и то, с чем связано время или, иначе, число операций - уровень сложности. «Нас будут интересовать не только количественные характеристики, но и некоторые функциональные моменты, - уточняет математик. - Например, каким образом растет сложность при росте объема данных».
Михаил Случ предлагает вернуться к первой задаче. Достаточно быстро коллеги приходят к выводу, что самый простой способ решения - последовательное сравнение нужного портрета со снимками из представленного массива. «Сколько действий при этом необходимо совершить? - спрашивает Михаил Ильич. - При самых неудачных обстоятельствах - пятьдесят». Во второй задаче, по сути, аналогичной первой, но с большим объемом данных, действий соответственно тоже на порядок больше - до двухсот. «Число действий пропорционально числу фотографий», - подводит итог математик.
Следующая задача, оказавшаяся для участников мастер-класса сложнее, - поиск совпадающих лиц. Как и в предыдущем случае, коллеги предлагают, двигаясь по цепочке, сравнивать первый снимок со всеми остальными. В случае если совпадение не будет найдено, необходимо перейти к следующему снимку и проделать аналогичные действия сравнения. «Все ли снимки придется сравнивать?» - интересуется Михаил Ильич. - «Нет. Если мы сравнили первую фотографию с десятой, то десятую с первой сравнивать уже не придется». Количество клеток в квадрате составляет N в квадрате. При наличии пятидесяти снимков количество клеток составляет две тысячи пятьсот, из которых, поясняет Случ, максимум необходимых для решения сравнений - тысяча двести пятьдесят. «Чуть меньше на самом деле, потому что диагональ придется из нашего рассмотрения исключить», - добавляет он.
Вместе с коллегами математик не просто обнаружил, что эта задача сложнее, чем задача поиска портрета, но и доказал, что она сложнее ровно в шесть раз. «Но и это еще не все. Если объем данных растет, то каким образом растет число операций?» - спрашивает Михаил Случ. Выдвинув несколько неверных предположений, коллеги находят ответ и на этот вопрос: число операций равно количеству данных в квадрате.
Математик предлагает перейти к более привычной задаче, с которой школьники сталкиваются уже во втором классе - умножение многозначных чисел. Он вызывает к доске одну из «учеников». Пока участница умножает 98 на 67, Михаил Случ просит проделать то же самое и остальных коллег, после чего обращается к залу, но уже с другим вопросом. Зрителям не нужно повторять навыки умножения. Им следует попытаться оценить: сколько шагов требуется для того, чтобы выполнить всем известный алгоритм умножения в столбик? Сколько элементарных действий находится внутри него и какие именно это действия? Ответ следует немедленно: умножение однозначных чисел и сложение. Михаил Ильич добавляет: «В каких-то тяжелых случаях еще происходит перенос в следующий разряд».
В это время «ученица» уже закончила умножение и приготовила ответ. Математик благодарит ее и проверяет результат. «Ответ сошелся! - восклицает Случ. - Это шесть тысяч пятьсот шестьдесят шесть».
«Сколько элементарных умножений придется проделать? - поворачивается к залу Михаил Ильич. - Четыре, еще сколько-то маленьких операций сложения, маленьких переносов, но умножение самое важное».
Затем Случ кардинально усложняет задачу. На этот раз нужно умножить два n-значных числа. На экране возникает алгоритм решения:

9 _ 9 9
*
9 _ 9 9
______________

8 9 _ 9 1
+
8 9 _ 9 1
+
- - - - -
+
8 9 _ 9 1
_____________

9 9 _ _ _ _ 8 1

В этом случае для решения задачи потребуется порядка трех n в квадрате операций, а число элементарных действий - умножение каждого числа на каждое - составит N в квадрате. Здесь математик решает провести параллель между данной задачей и задачей по поиску пары портретов. «Какая из этих задач сложнее, на ваш взгляд, а какая проще?» - спрашивает Случ.
Как выясняется, примерно одинаковые. В задаче с фотографиями сложность растет пропорционально квадрату числа фотографий, пропорционально числу пар. Во втором случае пропорционально квадрату разрядов. «Мы научились сравнивать непохожие задачи, - резюмирует Михаил Ильич. - Попробуем на этом не останавливаться».
Математик интересуется, знакомы ли участники с каким-либо более эффективным, нежели умножение в столбик, алгоритмом. Коллеги, улыбаясь, отвечают: да, можно воспользоваться калькулятором или компьютером.
Компьютер быстрее справится с решением задачи, чем человек с умножением в столбик. Но компьютер сделан и «научен» человеком. Тогда возникает другой вопрос: компьютер умножает быстрее человека лишь потому, что он быстрее выполняет требуемые операции, или потому, что внутри программы зашит какой-то более эффективный алгоритм? Вопрос о новом алгоритме умножения был весьма актуален на заре возникновения электронной вычислительной техники. Умножать в столбик умели еще четыре тысячи лет назад древние шумеры, сейчас человек часто пользуется тем же способом, разве что имеет дело с большими числами. «Умножение присутствует как составная часть в бесчисленном множестве алгоритмов, никак с умножением вообще не связанных. Поэтому для математиков было очень существенно понять: существуют ли более эффективные способы умножения?» - поясняет Михаил Ильич.
Например, в 1956 году Андрей Николаевич Колмогоров сформулировал «n-квадрат-гипотезу», суть которой состоит в том, что невозможно умножать быстрее, чем в столбик. Ровно через четыре года, в 1960-м, его гипотеза была опровергнута не каким-то маститым ученым, а молодым человеком, выпускником механико-математического факультета МГУ Анатолием Карацубой. Метод, предложенный Карацубой, понятен обычному семикласснику, нужно было свести умножение к некоему частному случаю и представить, что если умножение свести к возведению в квадрат, то получится более эффективный алгоритм. На интерактивной доске показана формула:
ab = ((a+b)2 - (a-b)2) / 4, где (a+b)2 - квадрат суммы, где (a-b)2 - квадрат разности.
«Не правда ли, необычный ход? - заявляет Случ. - Математика - это искусство видеть возможности». Дело оставалось за малым. Нужно было изобрести действительно простой алгоритм возведения в квадрат, с чем Карацуба успешно справился. В компьютерных программах реализован именно его алгоритм.
Пообещав в начале мастер-класса двигаться от простого к более сложному, Михаил Ильич сдержал свое обещание, что, как оказалось, вовсе не означало перехода к каким-то невероятным с математической точки зрения задачам. «Следующая задача пришла прямо из детского сада», - объявил Михаил Ильич.
Математик ставит на стол три стержня с табличками-номерами, на одном из стержней - пирамидка из трех разноцветных колец разного диаметра. Игра известна под названием «Ханойская башня». Придумал ее французский математик Эдуард Люка в далеком 1883 году. Задача - перенести все кольца пирамиды на соседний пустующий стержень, соблюдая при этом два правила: переносить по одному кольцу и не устанавливать кольцо большего диаметра на меньшее. Коллеги математика получили несколько наборов «Ханойской башни» и по просьбе Михаила Случа разбились на группы. Михаил Ильич предложил им начать игру, а сам вновь обратился к залу. Под активные комментарии из зала математик переставляет кольца, пока наконец в соответствии с условиями игры вся пирамидка не переходит с одного стержня на другой. Михаил Ильич предлагает разобрать решение задачи. «Нужно вспомнить самое начало моего мастер-класса, - говорит Случ. - О чайнике. Нужно свести задачу к предыдущей. Сколько нужно действий, чтобы переместить пирамиду высотой в два кольца? Три действия. Нижний диск - еще одно действие. И потом пирамиду из трех колец - семь действий. Вы видите, как растет сложность задачи? Кто может прогнозировать следующий результат?» Оказалось, пятнадцать действий. Михаил Случ просит дать ответ присутствующих в зале: «Сколько действий потребуется для того, чтобы переставить пирамиду высотой в шестьдесят четыре кольца?» Получив ответ - два в степени шестьдесят четыре и минус один, - он добавляет: «Вы видите взрывной, экспонициальный рост сложности. Если бы мы эту задачу пытались решать руками, одну операцию за одну секунду, нам с вами потребовалось бы пятьсот восемьдесят миллиардов лет».
Задачи, подобные приведенной, решаются не просто медленно - их решение требует почти бесконечного времени. Схожим образом устроены задачи, имеющие огромную практическую значимость. «Это задачи, которые реализуют так называемые переборные алгоритмы, - рассказывает Михаил Ильич. - Они присутствуют абсолютно во всех дисциплинах науки. Это задачи, связанные с управлением, многочисленные задачи, связанные с решением транспортных потоков, проектированием оптимальных сетей, биологические и химические задачи, связанные с синтезом новых соединений, наконец, задача расшифровки человеческого генома и защиты банковских транзакций».
Все эти задачи таковы, что для них не придумано на сегодняшний момент быстрых алгоритмов. Михаил Случ вновь касается вопроса: существуют ли эффективные алгоритмы для решения этих задач? Можно ли придумать какие-то способы, чтобы огромный перебор «два в степени» экспонициальной сложности превратить в так называемый полиномиальный перебор: n в квадрате, n в кубе и так далее? «На первый взгляд это детская проблема, - сообщает Михаил Ильич. - На самом деле в настоящий момент эта проблема формулируется как одна из важнейших. Может быть, даже с правом «задача номер один в математике». Речь идет о проблеме сокращения перебора - проблеме нахождения «быстрого» алгоритма для сложных задач P=NP».
Поясняя сложность, Михаил Ильич сравнивает P=NP-проблему с задачей из списка института Клее, которую не так давно решил математик Григорий Перельман. «Данная задача [P=NP] пока не поддается такому решению, - сообщает Михаил Ильич. - Может быть, кто-то из учеников ее решит. Если удастся это сделать, будут решены многие проблемы. Среди них, например, такая колоссальная проблема, как задача составления школьного расписания».
Мастер-класс подходит к завершению, Михаил Ильич спрашивает у участников о том, чем же они занимались. Звучат ответы: «Решали задачи и проблемы», «занимались простым и сложным», «сравнивали».
«Скажите, пожалуйста, есть ли такие вещи, такие понятия, как простое и сложное, в ваших предметах? - спросил математик. - Можете ли вы продолжить начатый мной ряд? Простые дроби. Простые числа. Простые и сложные проценты. Простые и сложные упражнения». Участники отвечали: есть, так в истории обнаруживаются простые и сложные истины, а в географии - однонациональные и сложнонациональные страны.
Поблагодарив коллег, Михаил Ильич задает еще один, последний, вопрос: «Нужно ли нам на своих предметах говорить о вопросах простоты и сложности с учениками?» На что коллеги единогласно ответили: да.