Выбрать книгу по жанру
Фантастика и фэнтези
- Боевая фантастика
- Героическая фантастика
- Городское фэнтези
- Готический роман
- Детективная фантастика
- Ироническая фантастика
- Ироническое фэнтези
- Историческое фэнтези
- Киберпанк
- Космическая фантастика
- Космоопера
- ЛитРПГ
- Мистика
- Научная фантастика
- Ненаучная фантастика
- Попаданцы
- Постапокалипсис
- Сказочная фантастика
- Социально-философская фантастика
- Стимпанк
- Технофэнтези
- Ужасы и мистика
- Фантастика: прочее
- Фэнтези
- Эпическая фантастика
- Юмористическая фантастика
- Юмористическое фэнтези
- Альтернативная история
Детективы и триллеры
- Боевики
- Дамский детективный роман
- Иронические детективы
- Исторические детективы
- Классические детективы
- Криминальные детективы
- Крутой детектив
- Маньяки
- Медицинский триллер
- Политические детективы
- Полицейские детективы
- Прочие Детективы
- Триллеры
- Шпионские детективы
Проза
- Афоризмы
- Военная проза
- Историческая проза
- Классическая проза
- Контркультура
- Магический реализм
- Новелла
- Повесть
- Проза прочее
- Рассказ
- Роман
- Русская классическая проза
- Семейный роман/Семейная сага
- Сентиментальная проза
- Советская классическая проза
- Современная проза
- Эпистолярная проза
- Эссе, очерк, этюд, набросок
- Феерия
Любовные романы
- Исторические любовные романы
- Короткие любовные романы
- Любовно-фантастические романы
- Остросюжетные любовные романы
- Порно
- Прочие любовные романы
- Слеш
- Современные любовные романы
- Эротика
- Фемслеш
Приключения
- Вестерны
- Исторические приключения
- Морские приключения
- Приключения про индейцев
- Природа и животные
- Прочие приключения
- Путешествия и география
Детские
- Детская образовательная литература
- Детская проза
- Детская фантастика
- Детские остросюжетные
- Детские приключения
- Детские стихи
- Детский фольклор
- Книга-игра
- Прочая детская литература
- Сказки
Поэзия и драматургия
- Басни
- Верлибры
- Визуальная поэзия
- В стихах
- Драматургия
- Лирика
- Палиндромы
- Песенная поэзия
- Поэзия
- Экспериментальная поэзия
- Эпическая поэзия
Старинная литература
- Античная литература
- Древневосточная литература
- Древнерусская литература
- Европейская старинная литература
- Мифы. Легенды. Эпос
- Прочая старинная литература
Научно-образовательная
- Альтернативная медицина
- Астрономия и космос
- Биология
- Биофизика
- Биохимия
- Ботаника
- Ветеринария
- Военная история
- Геология и география
- Государство и право
- Детская психология
- Зоология
- Иностранные языки
- История
- Культурология
- Литературоведение
- Математика
- Медицина
- Обществознание
- Органическая химия
- Педагогика
- Политика
- Прочая научная литература
- Психология
- Психотерапия и консультирование
- Религиоведение
- Рефераты
- Секс и семейная психология
- Технические науки
- Учебники
- Физика
- Физическая химия
- Философия
- Химия
- Шпаргалки
- Экология
- Юриспруденция
- Языкознание
- Аналитическая химия
Компьютеры и интернет
- Базы данных
- Интернет
- Компьютерное «железо»
- ОС и сети
- Программирование
- Программное обеспечение
- Прочая компьютерная литература
Справочная литература
Документальная литература
- Биографии и мемуары
- Военная документалистика
- Искусство и Дизайн
- Критика
- Научпоп
- Прочая документальная литература
- Публицистика
Религия и духовность
- Астрология
- Индуизм
- Православие
- Протестантизм
- Прочая религиозная литература
- Религия
- Самосовершенствование
- Христианство
- Эзотерика
- Язычество
- Хиромантия
Юмор
Дом и семья
- Домашние животные
- Здоровье и красота
- Кулинария
- Прочее домоводство
- Развлечения
- Сад и огород
- Сделай сам
- Спорт
- Хобби и ремесла
- Эротика и секс
Деловая литература
- Банковское дело
- Внешнеэкономическая деятельность
- Деловая литература
- Делопроизводство
- Корпоративная культура
- Личные финансы
- Малый бизнес
- Маркетинг, PR, реклама
- О бизнесе популярно
- Поиск работы, карьера
- Торговля
- Управление, подбор персонала
- Ценные бумаги, инвестиции
- Экономика
Жанр не определен
Техника
Прочее
Драматургия
Фольклор
Военное дело
Журнал «Компьютерра» № 6 от 14 февраля 2006 года - Компьютерра - Страница 36
Машины, работающие за полиномиальное время с подсказкой, кажутся гораздо мощнее, чем обычные машины без подсказки. Действительно, им нужно всего лишь проверить данный ответ, а обычной машине нужно его сначала найти. Однако вопрос о том, нельзя ли каждую недетерминированную машину Тьюринга превратить в детерминированную, до сих пор открыт. Собственно, это и есть знаменитая проблема равенства классов P и NP.
Учитывая сказанное выше об NP-полных задачах, проблема будет решена положительно, если найдется полиномиальный алгоритм хотя бы для одной NP-полной задачи. Но пока таковых нет даже в перспективе; более того, нет даже субэкспоненциальных алгоритмов (то есть тех, которые бы работали за время, меньшее 2 cn , но большее полиномиального – например, за 2 v n~). Такие алгоритмы существуют только для задач, которые подозревают в том, что они занимают промежуточное положение – и не полиномиальные, и не NP-полные. Такова, например, проблема изоморфизма графов: по двум данным графам понять, можно ли перевести вершины одного графа в вершины другого так, чтобы ребра переходили в ребра. Впрочем, подозрения могут и не оправдаться: например, одним из самых громких результатов последних лет был полиномиальный алгоритм для задачи проверки числа на простоту. Примечательно, кстати, что проверка на простоту оказывается принципиально проще, чем разложение на множители[Возможно, это покажется менее странным, если напомнить, что сложность измеряется от длины входа. А длина входа в данном случае – это длина числа в двоичной записи, то есть примерно его логарифм. И алгоритм, чтобы быть полиномиальным от длины входа, должен быть логарифмическим от величины числа, которое нужно проверить на простоту].
Теперь, когда мы поняли формулировку задачи, перейдем к ее обсуждению.
Первое: почему она так сложна? Конечно, можно сказать «потому что вот уже полвека пытаются и никак не могут», но есть и более интересные и глубокие причины. Я уже упоминал в сноске, что если рассмотреть «классы с оракулами», то для разных оракулов ответ получится разным. Переход от обычных классов к классам с произвольными оракулами называется релятивизацией. Большинство существующих идей и методов доказательства теорем в теории сложности вычислений выдерживают релятивизацию, то есть могут быть обобщены на случай произвольного оракула. Стало быть, все эти идеи и методы для доказательства (не)равенства P и NP неприменимы! Более того, в 1996 году Александр Разборов (наш соотечественник, лауреат премии Неванлинны) и Стивен Рудих (Steven Rudich) ввели класс так называемых естественных доказательств и показали, что нет естественных доказательств, которые бы позволили доказать, что SAT не решается за полиномиальное время. Под впечатлением таких результатов некоторые математики начинают склоняться к тому, что несовпадение P и NP может оказаться недоказуемым в рамках существующей аксиоматики. В 2002 году проводился даже опрос на эту тему. Из ста исследователей на вопрос «как вы считаете, равны ли P и NP?» 61 ответил «нет», 9 – «да», 22 – «сомневаюсь» и 8 – «наверное, вопрос не зависит от существующей аксиоматики».
Второе: что будет следовать из различных решений этой задачи. Если P не равно NP, все в порядке. Небо не упадет на землю, Запад не сойдется с Востоком, а пришествие Зверя будет отложено до лучших времен. А вот если P=NP, то начнется такое… Практика показывает: на деле «полиномиальное» означает «относительно легко решаемое». И если появятся способы относительно быстро решать NP-полные проблемы – могут возникнуть очень серьезные проблемы уже вне математики. Например, современная практическая криптография, основанная на RSA или DES/AES, окажется бесполезной. К чему это приведет, любой человек, знакомый с тем, как нынче хранится защищенная информация (номер вашей банковской карточки, пароль к вашему почтовому ящику и т. п.), легко может себе представить. Кроме того, это повлечет за собой серьезные изменения в наших представлениях об иерархии сложностных классов: целый бесконечный набор классов, которые сейчас считаются разными – так называемая полиномиальная иерархия, – «схлопнется» до одного-единственного класса P, и многие другие весьма правдоподобные предположения окажутся неверными. И все же, в отличие от гипотезы Римана, здесь нельзя сбрасывать со счетов вероятность того, что классы окажутся равными: уже много открытий чудных приготовила нам теория сложности, и как знать – может быть, наша уверенность в том, что P не равно NP, – тоже не более чем иллюзия…
Подведем итоги. Проблема равенства или неравенства классов P и NP – одна из центральных проблем современной информатики. Как мы только что видели, на предположении о неравенстве этих классов держится очень большая часть повседневной практической безопасности каждого из нас. Так что миллион за такую проблему – совсем не много, пусть даже платят за любое из двух решений – что за «равно», что за «не равно»[Правда, я не знаю, заплатят ли миллион за доказательство того, что это (не)равенство нельзя доказать. Думаю, да]. А еще эта проблема, наверное, одна из самых доступных для понимания непрофессионального математика – что порождает поток дилетантских, очевидно неверных решений. Надеюсь, читатели «КТ» будут умнее и если уж и придумают решение, то такое, чтобы о нем стоило написать отдельную подробную статью, а лучше – книгу.
NP-полнота как генератор драйва
Cреди NP-полных задач есть и более веселые экземпляры, нежели упоминаемые в статье Сергея Николенко классические проблемы математики. Оказывается, точно такой же полнотой обладают и стратегии некоторых популярных игр. Самые яркие примеры: «Тетрис» и «Сапер» (он же «Минер», «Minesweeper»), пожирающие с одинаковым аппетитом что рабочее, что свободное время. Связаны ли гипнотизирующие свойства игр с (предполагаемым) отсутствием для них простого алгоритма победы – вопрос из области психологии, а психологи, как известно, не склонны к однозначным ответам. Но не так давно было строго математически доказано: нахождение полиномиальных алгоритмов для этих игр повлечет снятие вопросительного знака в гипотезе P=?NP, а стало быть, и падение современной криптографии (по крайней мере, концептуально). В этом смысле «Тетрис» и «Сапер» ничем не хуже зловещего коммивояжера, согласного двигаться лишь по наиболее дешевому маршруту.
NP-полны многие задачи, связанные с даже не с обычным, а с сильно упрощенным офлайновым «Тетрисом», когда поток фигурок, валящихся с потолка, заранее известен, а каждую фигурку можно переворачивать и двигать сколько угодно раз. Среди этих задач – максимизация числа заполненных строк, а также минимизация высоты, на которой в процессе игры находится самый верхний квадратик уже уложенных фигурок (подробнее см. работу исследователей из MIT, arXiv:cs:CC/0210020).
Очень красиво доказывается NP-полнота стратегического планирования для «Сапера». Стратегия в нем основана на решении такой задачи – выяснить, допустима ли заданная конфигурация игры, то есть расстановка цифр, флажков, открытых и закрытых квадратиков (игра идет на поле произвольного размера). Допустимость означает, что эта конфигурация действительно возникает при некотором начальном расположении мин. Именно проблема установления допустимости NP-полна, а доказательство получено путем сведения этой задачи к классической NP-полной проблеме SAT. Но самое интересное, разумеется, не «что», а «как».
Ричард Кей из Университета Бирмингема (Richard Kaye) свел «Сапера» к SaT следующим образом. В SaT речь идет о поведении булевой формулы, то есть схемы, реализуемой гейтами вида "И", «ИЛИ», «НЕ». Кей придумал несколько экзотических конфигураций «Сапера», которые напрямую в самом буквальном смысле реализуют гейты и соединяющие их проводники. Из таких конфигураций можно собрать любую логическую схему. По сути, игровое поле превращается в компьютер! Квадраты поля принимают значения T (есть мина) или F (нет мины). Проверка допустимости конфигураций, реализующих логические и другие конструктивные элементы, интерпретируется как выполнение соответствующих им функций. На рис. 1 показано, как устроен провод, на рис. 2 – вентиль "И" (оригиналы рисунков см. на сайте Кея).
- Предыдущая
- 36/37
- Следующая