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

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

Рейтинг LiveLib

3,7

8 оценок

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

Ваша оценка

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

Рецензии

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