Это новая версия страницы. Часть функций ещё в работе — мы добавляем их постепенно.

Луис Фернандо Ареан - Том 43. Существуют ли неразрешимые проблемы? Математика, сложность и вычисление

Ваша оценка

3,7

(8)

Том 43. Существуют ли неразрешимые проблемы? Математика, сложность и вычисление

Name: Том 43. Существуют ли неразрешимые проблемы? Математика, сложность и вычисление
Rating: 3.7 (8 reviews)
Author: Луис Фернандо Ареан
ISBN: 978-5-9774-0682-6, 978-5-9774-0774-8

Луис Фернандо Ареан

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

Издательство:

Де Агостини

Серия:

Мир математики

ISBN:

978-5-9774-0682-6, 978-5-9774-0774-8

Год издания:

2014

Язык:

Русский

144 стр.

Формат 70х100/16.

Тираж 28 600 экз.

Твердый переплет.

Возрастные ограничения:

12+

Рейтинг LiveLib

3,7

8 оценок

5
13%
4
63%
3
13%
2
13%
1
0%

Ваша оценка

Прочитали 11Хотят прочитать 41

Рецензии

sq
18 мая 2022
Книга о теории сложности. Для меня это офигительно -- несказанно! -- интересная тема, которая лежит за границами моего понимания. Прочитал уже дюжину изложений теории, но моих мозгов хватает только на самое начало. Вот и в этот раз начал путаться в логике уже где-то к концу третьей главы. Но дочитал. Дело в том, что меня абсолютно завораживает переплетение бесконечностей в стиле Кантора. Интуитивно ясно, что есть задачи какой угодно сложности, и самые сложные из них дают начало следующему классу ещё более сложных задач: P --> NP --> EXP --> NEXP --> ... --> ... --> ... Понятно, что этот ряд бесконечен, что для любого суперквантового компьютера найдётся задача, на которой он сломается. А между тем мы всё ещё топчемся где-то в районе P, и неизвестно, доберёмся ли когда-нибудь хотя бы до NP. В этом смысле проблемы открываются не только математические, но и философские. Луис Фернандо Ареан и об этом рассказал. Книга представляет собой обзор теории. Она должна представлять собой толстый том, но за такое чтение я совсем не стал бы браться, так что всё нормально.
Снимаю шляпу перед Скоттом Ааронсоном. Он всё это понимает в деталях и даже составил список классов задач в соответствии с их сложностью -- Зоопарк сложностей. В нём более 400 зверей.
Неожиданно почувствовал на пальцах, что такое доказательство с нулевым разглашением. Прежде понимал только теоретически. Может быть, это оттого, что Луис Фернандо Ареан заменил всем надоевших Алису и Боба Ахиллом с Брисеидой :)
Неожиданностью явилась также и вполне, казалось бы, лежащая на поверхности идея о том, что если у нас есть машина для путешествия в прошлое, то мы можем прочитать любое сообщение, зашифрованное RSA или подобным методом.
Стойкость шифра обеспечивается сложностью разложения большого числа на множители. Если у нас есть какой-нибудь (возможно, вполне тупой) алгоритм для этой операции, расшифровку ограничивает только лишь нехватка времени. Однако если мы можем отскочить на некоторое время назад, мы сможем повторно использовать время, т.е. у нас его хватит на что угодно, в том числе и на то, чтобы разложить любое число на множители.
Дело за малым: построить машину времени. Говорят, на московском заводе Рено будут строить какие-то импортозамещённые автомобили. Лучше бы наладили производство машин времени :)
Да, теория сложности слишком для меня сложна. В этой жизни я её точно не постигну. Но при случае прочитаю о ней что-нибудь ещё :)
Читать далее
15 понравилось
0
219