Золотой билет. P, NP и границы возможного - Лэнс Фортноу
Книгу Золотой билет. P, NP и границы возможного - Лэнс Фортноу читаем онлайн бесплатно полную версию! Чтобы начать читать не надо регистрации. Напомним, что читать онлайн вы можете не только на компьютере, но и на андроид (Android), iPhone и iPad. Приятного чтения!
Шрифт:
Интервал:
Закладка:
В середине 1960-х формальное определение эффективного алгоритма появилось сразу в двух работах: «Пути, деревья и цветы» Джека Эдмондса и «Внутренняя вычислительная трудность функций» Алана Кобэма.
Работа Эдмондса получила широкую известность благодаря тому, что в ней впервые был предложен эффективный алгоритм для задачи о числе паросочетаний, рассмотренной нами в третьей главе. В главе под названием «Отступление» ученый рассуждает об экспоненциальной и алгебраической сложности, предостерегая в то же время от использования слишком жестких критериев эффективности.
«Необходимо пояснить, что же все-таки понимается под эффективным алгоритмом <…> Я не готов сейчас дать строгое определение и сформулировать какие-то технические требования; вопрос этот находится за рамками данного исследования <…> С практической точки зрения разделять задачи на алгебраические и экспоненциальные гораздо важнее, чем на вычислимые и не вычислимые <…> Введение жесткого критерия могло бы повлечь за собой негативные последствия и помешать развитию алгоритмов, про которые невозможно с уверенностью утверждать, удовлетворяют они данному критерию или нет <…> Важно также понимать, что, принимаясь за поиски хороших, практических алгоритмов, разумно было бы для начала задаться вопросом об их существовании».
Класс алгебраических задач, введенный Эдмондсом, – это и есть класс P: задачи, которые можно решить эффективно. Подчеркивая тот факт, что для постановки вопроса о равенстве P и NP и других подобных задач четкое определение иметь необходимо, ученый в то же время призывает не отказываться от менее формального понятия вычислительной эффективности, и при написании этой книги я старался действовать именно так.
Кобэм в своей работе независимо от Эдмондса вводит тот же класс задач и приводит аналогичные рассуждения о пользе четкого определения.
По ряду причин желание ввести класс P выглядит вполне закономерным. Формализация описания классов вычислительных машин, как правило, приводит нас к четкому определению соответствующих классов функций, так что можно не бояться исказить суть класса P при переходе от интуитивного определения к математическому.
Понятие класса P, так же как и понятие вычислимости, не зависит от конкретной вычислительной модели.
Кобэм тоже считает своим долгом предупредить:
«Этот вопрос напоминает нам о другом, с которым он теснейшим образом связан: о необходимости формализовать понятие эффективности. Впрочем, в данном случае эффективность следует рассматривать под несколько другим углом, поскольку на первый план здесь выходят физические характеристики вычислительного процесса».
Ученый, вероятно, отдавал себе отчет в том, что когда-нибудь появятся вычислительные модели, не укладывающиеся в его классификацию. Понятие эффективности нельзя зафиксировать раз и навсегда, и создание рандомизированных, а затем и квантовых алгоритмов – лишнее тому подтверждение.
В 1971 году Стивен Кук сформулировал понятие класса NP (задачи, решение которых можно эффективно проверить), а также поставил вопрос о равенстве P и NP и нашел первую NP-полную задачу. Годом позже Ричард Карп доказал NP-полноту для целого ряда известных математических проблем.
Выступление Карпа стало самым знаменательным событием на Конференции по вопросам сложности вычислений, проведенной в 1972 году Исследовательским центром IBM имени Томаса Дж. Уотсона. Будущее нового направления активно обсуждалось на итоговом заседании организаторской комиссии. Одной из главных тем был вопрос о том, как из горстки разрозненных результатов – нескольких алгоритмов и нижних оценок сложности – построить единую теорию. Участники заседания, среди которых был и Ричард Карп, вряд ли отдавали себе отчет, что ответ на этот вопрос находится у них перед глазами – в работах Кука и самого Карпа, описывающих классы P и NP, понятие сводимости, а также свойство, которое позже назовут NP-полнотой.
Карп прекрасно понимал, что новой области науки требуется хорошее название:
«Термин „вычислительная сложность“ представляется мне чересчур широким – по крайней мере до тех пор, пока мы не включили сюда работы Блюма и его последователей. „Реальная вычислительная сложность“ подходит больше для какой-нибудь практической, инженерной дисциплины, ну а „сложность компьютерных вычислений“ вообще неверно отражает суть».
В конце концов победило название «вычислительная сложность». Вопрос о равенстве P и NP приобрел огромное значение и быстро затмил все остальные направления исследований в данной области. Абстрактная теория сложности отошла на второй план; даже Блюм переключился на криптографию и верификацию программ. В 1995 году ученый получил премию Тьюринга за свою активную исследовательскую деятельность в 1960–1980-х годах. Когда много лет спустя его спросили, почему он все-таки решил сменить направление, Блюм ответил: «Потому что Кук был прав».
В СССР проблемами теоретической кибернетики занимались многие выдающиеся ученые. Мы подробно остановимся на трех из них; все они являются представителями различных подходов к методу перебора.
1. Сергей Всеволодович Яблонский первым применил перебор для поиска минимальных схем, реализующих дискретные функции. К сожалению, его самонадеянность в сочетании с огромным влиянием, которое он приобрел в научной среде, тормозили развитие теории вычислительной сложности.
2. Андрей Николаевич Колмогоров – крупнейший ученый в истории русской науки – предложил в качестве меры сложности алгоритмическую информацию.
3. Ученик Колмогорова Леонид Анатольевич Левин независимо от Кука сформулировал проблему равенства классов P и NP и пришел к понятию NP-полноты. На родине защитить диссертацию он не смог по политическим причинам.
В Советском Союзе исследования в области теории вычислений проводились в рамках теоретической кибернетики. Активное развитие этой области началось в 1950-х годах, когда электронные вычислительные машины были взяты на вооружение военными. Сергей Яблонский родился в 1924 году в Москве. Вернувшись с фронта после окончания Второй мировой войны, он продолжил изучать математику в Московском государственном университете. В 1953 году Яблонский защитил кандидатскую диссертацию под руководством Петра Сергеевича Новикова, который одним из первых в СССР начал заниматься проблемами вычислимости. Вместе с Алексеем Андреевичем Ляпуновым, также работавшим под руководством Новикова, Яблонский проводил в МГУ семинары по вопросам реализации булевых функций. Яблонский и Ляпунов организовывали и направляли всю исследовательскую деятельность в области теории вычислений.
Проблема выполнимости, упомянутая в четвертой главе, касается логических формул, т. е. формул, в которых основными операциями являются «И», «ИЛИ» и «НЕ». На самом деле любой вычислительный процесс можно представить в виде набора таких операций, или, другими словами, в виде схемы из элементов «И», «ИЛИ» и «НЕ». Одни задачи решаются схемами небольшого размера, для других необходимо огромное число элементов. Возникает понятие схемной сложности, и в начале пятидесятых Яблонский этим понятием заинтересовался.
Прочитали книгу? Предлагаем вам поделится своим отзывом от прочитанного(прослушанного)! Ваш отзыв будет полезен читателям, которые еще только собираются познакомиться с произведением.
Уважаемые читатели, слушатели и просто посетители нашей библиотеки! Просим Вас придерживаться определенных правил при комментировании литературных произведений.
- 1. Просьба отказаться от дискриминационных высказываний. Мы защищаем право наших читателей свободно выражать свою точку зрения. Вместе с тем мы не терпим агрессии. На сайте запрещено оставлять комментарий, который содержит унизительные высказывания или призывы к насилию по отношению к отдельным лицам или группам людей на основании их расы, этнического происхождения, вероисповедания, недееспособности, пола, возраста, статуса ветерана, касты или сексуальной ориентации.
- 2. Просьба отказаться от оскорблений, угроз и запугиваний.
- 3. Просьба отказаться от нецензурной лексики.
- 4. Просьба вести себя максимально корректно как по отношению к авторам, так и по отношению к другим читателям и их комментариям.
Надеемся на Ваше понимание и благоразумие. С уважением, администратор knigkindom.ru.
Оставить комментарий
-
Гость Светлана26 июль 20:11
Очень понравилась история)) Необычная, интересная, с красивым описанием природы, замков и башен, Очень переживала за счастье...
Ледяной венец. Брак по принуждению - Ульяна Туманова
-
Гость Диана26 июль 16:40
Автор большое спасибо за Ваше творчество, желаю дальнейших успехов. Книга затягивает, читаешь с удовольствием и легко. Мне очень...
Королевство серебряного пламени - Сара Маас
-
Римма26 июль 06:40
Почему героиня такая тупая...
Попаданка в невесту, или Как выжить в браке - Дина Динкевич
