Юдин Д.Б., Юдин А.Д. Математики измеряют СЛОЖНОСТЬ № 23. Изд. стереотип.

Оглавление

Предисловие

В послевоенные годы в различных областях науки – в автоматическом регулировании, математической экономике, биологии и ряде инженерных дисциплин – возникла проблема исследования феномена сложности. Проектирование современной техники, планирование на разных уровнях, управление системами, объяснение и прогнозирование эволюционных процессов сталкиваются с трудностями одной и той же природы. Во всех этих целенаправленных операциях требуется установить принципиальную разрешимость появляющихся здесь задач, а для алгоритмически разрешимых задач – выяснить, насколько они физически осуществимы. Другими словами, необходимо оценить минимальные объемы тех или иных ресурсов, требуемых для реализации решения. Анализ этих проблем и составляет сущность формирующейся в последние десятилетия дисциплины – теории сложности.

Теория сложности стоит на стыке философии, логики и различных разделов естественных, технических и общественных наук. В разработке категории сложности, в изучении свойств компонент сложности и в совершенствовании методов оценки составляющих сложности заинтересованы специалисты самых различных дисциплин. И с ростом масштабов производства и уровней управления, с расширением горизонтов исследований эта заинтересованность все возрастает. Трудно переоценить значение своевременного ответа на вопрос, в какой мере реально достижение той или иной цели и какие для этого необходимы ресурсы. Советские ученые, и в первую очередь академик А.Н.Колмогоров и его ученики, первыми проложили пути к формированию категории сложности, к исследованию ее свойств и перспектив ее приложений. В последующем стало ясно, что логическое понятие алгоритмической сложности является важной, но не единственной характеристикой категории сложности. Появились и другие направления исследований, связанные с вычислительной сложностью, информационной сложностью, энергетической сложностью, сложностью схем, сложностью обработки информации и др. Различные компоненты сложности оценивают разные аспекты трудоемкости и ресурсоемкости достижения тех или иных целей. Среди работ по различным составляющим сложности фигурируют и работы авторов настоящей книги.

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

Предлагаемая вниманию читателей книга представляет собой достаточно популярное изложение этой отнюдь не элементарной проблематики, написанное специалистами для неспециалистов. Здесь охвачены различные разделы теории сложности и обсуждается достаточно широкий диапазон ее возможных приложений. Авторы, как они сами об этом заявляют, вынуждены были в угоду доступности изложения несколько поступиться формальной строгостью формулировок. Это, однако, никоим образом не повлияло на познавательную ценность авторской аргументации. Следует все же отметить, что не все приведенные в книге истолкования перспектив теории сложности могут быть безоговорочно восприняты критически настроенным читателем. Но ведь постановка острых вопросов и выявление и обсуждение правдоподобных гипотез стимулируют целеустремленное движение к истине. Уместно вспомнить замечание В.Райгли о том, что из двух искателей истины, придерживающихся одного и того же мнения, по крайней мере один лишний.

Представляется, что настоящая книга дает основание для полезных дискуссий по одной из кардинальных проблем современной науки.

Отрывок из книги

ЧТО ТАКОЕ КАТЕГОРИЯ "СЛОЖНОСТЬ" И ЗАЧЕМ ОНА НУЖНА?

Интуитивные определения сложности

В толковом словаре Владимира Даля (т.IV, с.216) приведено следующее определение термина "сложность": "Сложность – свойство и состояние "сложенного"; совокупность, весь состав, общность составного". Далее следуют пояснительные примеры. "Сложность машины затрудняет приложение к делу. По сложности дела этого следователи спутали его".

Вряд ли можно определение и пояснения Даля принять за образец формальной четкости и строгости. Однако в разговорной речи и в художественной литературе, при обсуждении повседневных дел и многих производственных вопросов использование термина "сложность", как правило, не вызывает недоразумений. В зависимости от контекста, в котором фигурирует термин "сложный", его истолковывают как "большой", "трудоемкий", "запутанный", "непредсказуемый" и т.д.

Большее внимание определению понятия "сложность" должно быть, естественно, уделено в науке, технике, экономике. Нетрудно представить себе ситуации, в которых сложность систем, явлений, процессов следует измерять и сравнивать. Тем не менее в работах, в которых подчеркивается необходимость и важность категории сложности в задачах управления, проектирования и организации, обычно не уточняется и не формализуется это понятие. Молчаливо предполагается, что специалисты, занимающиеся одним и тем же кругом проблем, одинаково понимают и истолковывают этот термин. Так, инженеры на эвристическом уровне подразумевают под сложной системой систему из большого числа взаимосвязанных элементов, поведение которой трудно предсказуемо. Специалисты по теории принятия решений называют сложной систему, цели поведения которой противоречивы и не всегда поддаются формализации. Математики-прикладники под сложной проблемой понимают труднорешаемую задачу, анализ которой связан с чрезмерно большим количеством вычислений. Биологи связывают понятие "сложность организма" со степенью его организации.

До последних лет отсутствие четких определений понятий "сложная система", "сложная задача", "сложный процесс" обычно не мешало их распознаванию и исследованию. Но уже сейчас можно указать математические и прикладные проблемы, для постановки и решения которых недостаточно смутных эвристических представлений. Все настоятельней ощущается необходимость в четком определении категории "сложность" и уточнении различных ее аспектов применительно к разным системам и задачам.

Подчеркнем с самого начала, что сложность систем, явлений, процессов вряд ли может быть охарактеризована единым показателем. Сложность-категория многогранная. В различных проблемах проявляются различные составляющие сложности. Системы или процессы, сложные в одних отношениях и в определенных ситуациях, могут оказаться несложными в других отношениях и в другой обстановке. Целесообразно рассматривать статическую и динамическую сложность, сложность объекта и сложность функционирования, внутреннюю сложность системы и сложность управления ею. В зависимости от класса исследуемых систем (от их назначения и условий функционирования) системы сравниваются и оцениваются по таким компонентам, как сложность описания (моделирования), алгоритмическая сложность, энергетическая сложность, информационная сложность и др. Обсуждаются и другие характеристики сложности, предназначенные для исследования и оценки биологических, экономических и социальных систем. Эти работы относятся к наиболее трудным разделам теории сложности. Они еще недостаточно формализованы и по ним среди специалистов еще не достигнуто единого мнения.

В настоящей работе кратко излагаются результаты современной теории сложности, представляющие, с нашей точки зрения, интерес для исследования закономерностей целеустремленных систем и целенаправленных процессов. Особое внимание уделяется аспектам теории сложности, важным для постановки и анализа задач принятия решений, с которыми так или иначе связаны основные проблемы планирования, управления, проектирования и организации. Естественно, что мы не можем претендовать на сколь-нибудь полное изложение основных результатов и перспектив этой новой интенсивно развивающейся дисциплины.

Оговоримся с самого начала, что по необходимости мы будем пренебрегать формальной строгостью изложения в угоду доступности и отдадим предпочтение качественному обсуждению материала по сравнению с формальным анализом.

Сложность и неформальные проблемы

Приведем неформальные высказывания некоторых видных ученых о роли понятия "сложность" в познании закономерностей реального мира.

Известные советские философы Б.В.Бирюков и В.С.Тюхтин пишут: "С понятием о сложности и сложных системах мы встречаемся фактически во всех – или почти во всех – науках; сложность – это общенаучное понятие, приближающееся по своему "статусу" к философской категории" [2, с.219]. Это заключение отражает реальную динамику познавательного процесса последних десятилетий.

Один из величайших математиков XX века Джон фон Нейман говорил, что теория сложности является "предпосылкой к пониманию процессов обучения и развития" и что "понятие сложности, несмотря на его prima facie количественный характер, может в действительности выражать нечто качественное – иметь принципиальное значение" [32, с.92].

Специалист по прикладной математике Дж.Касти в монографии из серии, основанной Международным институтом прикладного системного анализа в Вене, приводит следующее определение одной из важных компонент сложности. "Сложность управляемых систем, по существу, является мерой вычислительных возможностей, необходимых для реализации заданного поведения. В идеале математическая теория сложности должна достигнуть уровня, аналогичного уровню развития теории вероятностей. В то время как вероятность можно рассматривать как меру неопределенности в данной ситуации, сложность можно трактовать как меру понимания поведения системы" [18, с.57–58).

Стаффорд Бир – бывший президент Британского общества по исследованию операций – называет сложность основным свойством реального мира. Он говорит: "Сложность становится проблемой века, точно так же, как умение обрабатывать природные материалы было проблемой жизни и смерти для наших праотцов" [1, с.8]. Обилие информации, порождаемое сложностью современной жизни, представляет собой разновидность загрязнения окружающей среды. Слова-паразиты, понятия-паразиты, бесчисленные, ни о чем не говорящие данные, ложные посылки, организационные структуры, не соответствующие объективным условиям времени и места, обезоруживают человечество в борьбе со "сложностью мира". Основной способ преодоления сложности, по Биру, – создание и изменение метасистемных управляющих механизмов. Отсюда задача теории сложности – разработка емких и экономных понятий, отражающих различные аспекты категории "сложность", облегчающих обмен информацией и побуждающих к изменению образа мышления в соответствии с развитием объективной реальности.

Математические задачи теории сложности

В современной математической логике исследуются важные и трудные задачи, решение которых может иметь далеко идущие практические последствия. Это задачи, связанные с одной из наиболее интересных особенностей математического творчества – с доказательством невозможности определенных построений. Пожалуй, наиболее значительными результатами такого рода стали полученные в тридцатые годы А.Черчем, а затем в сороковые и пятидесятые годы А.А.Марковым, Э.Постом, П.С.Новиковым и в 1969 г. Ю.В.Матиясевичем доказательства алгоритмической неразрешимости некоторых массовых проблем (классов задач) математической логики и алгебры.

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

Помимо алгоритмической неразрешимости, существует еще, если можно так выразиться, физическая неразрешимость, т.е. невозможность решения, связанная не с отсутствием разрешающего алгоритма, а с ограниченностью наших временных и материальных ресурсов. Минимальную величину времени, памяти, энергии и других ресурсов, гарантирующую решение требуемого качества любой задачи исследуемого класса (любой индивидуальной задачи рассматриваемой массовой проблемы), естественно принять за определение соответствующей компоненты сложности массовой проблемы. Аналогичные рассуждения позволяют получить умозрительные представления о составляющих сложности различных систем. Эти величины характеризуют, в частности, степень физической реализуемости постижения закономерностей состояния и поведения системы.

Пренебрежение к физической реализуемости решения алгоритмически разрешимых проблем отнюдь не способствует взаимопониманию теоретиков и практиков. Многие логически безупречные построения не воспринимаются инженерами, экономистами и физиками в силу их предельней абстрактности. Абстракция потенциальной осуществимости, которая, по А.А.Маркову [29], состоит в отвлечении от реальных границ наших конструктивных возможностей, обусловленных ограниченностью нашей жизни в пространстве и времени, приемлема для построения оснований математики, но не приемлема для анализа практических задач.

Существуют убедительные доводы в пользу того, что физические процессы или материальные объекты не могут характеризоваться такими числами, как 10¹⁰⁰ и более. Реалиста-прикладника не интересует различие между числами 10^l00 и 10¹⁰⁰!. За тем и другим числом ничего реального нет. Поэтому глубокие формальные исследования, которые связывают характеристики систем с числами подобного порядка, не способствуют сокращению разрыва между теорией и практикой.

Важная задача теории сложности – дополнить доказательства принципиальной реализуемости алгоритмов или систем оценкой их физической реализуемости – оценкой минимальных величин различных ресурсов, необходимых для этого.

Об авторах

Родился в Днепропетровске. Во время учебы в школе часто участвовал в городских, областных и республиканских математических олимпиадах и каждый раз попадал в число победителей. В 1936 г. по окончании 10 класса (за 9 лет) был без экзаменов зачислен на 1-й курс механико-математического факультета Днепропетровского государственного университета. С июля 1941 г. – участник Великой Отечественной войны. Демобилизовался в 1975 г. в звании инженер-полковника. В 1948 г. защитил в НИИ-5 ГАУ диссертацию на соискание ученой степени кандидата технических наук, а в 1957 г. в Академии им. Фрунзе – диссертацию на соискание ученой степени доктора технических наук. Ученое звание старшего научного сотрудника присвоено в 1951 г., профессора – в 1962 г. Награжден двумя орденами и 16 медалями. В течение ряда лет консультировал Госплан СССР. Более 35 лет являлся профессором экономического факультета МГУ, с 1994 г. – профессор Высшей школы экономики. В 1982 г. Международным обществом по математическому программированию и Американским математическим обществом присвоена премия имени Фалкерсона по дискретной математике. В 1993 г. Д.Б.Юдину присвоено звание "Заслуженный деятель науки и техники РСФСР". В 1994 г. он избран действительным членом Нью-Йоркской академии наук.

Д.Б.Юдиным опубликовано 18 монографий по различным разделам математического программирования, по теории и методам принятия решений, а также более 200 научных работ в различных периодических изданиях.

Александр Давидович ЮДИН (род. в 1950 г.)

Родился в Москве. В 1967 г. окончил школу и поступил на 1-й курс механико-математического факультета Московского государственного университета. В 1970 г. перевелся на экономический факультет, который закончил в 1973 г. В 1980 г. защитил в ЦЭМИ АН СССР диссертацию на соискание ученой степени кандидата экономических наук. Ученое звание старшего научного сотрудника присвоено в 1985 г., а в 2003 г. – звание профессора Института коммерции и права. А.Д.Юдиным опубликовано 5 монографий по различным разделам математического программирования, по теории и методам принятия решений, а также около 100 научных работ в различных периодических изданиях.