Рецензия на книгу

• 

  sq18 мая 2022 г.

  Книга о теории сложности.
  Для меня это офигительно -- несказанно! -- интересная тема, которая лежит за границами моего понимания. Прочитал уже дюжину изложений теории, но моих мозгов хватает только на самое начало. Вот и в этот раз начал путаться в логике уже где-то к концу третьей главы. Но дочитал.
  Дело в том, что меня абсолютно завораживает переплетение бесконечностей в стиле Кантора. Интуитивно ясно, что есть задачи какой угодно сложности, и самые сложные из них дают начало следующему классу ещё более сложных задач: P --> NP --> EXP --> NEXP --> ... --> ... --> ... Понятно, что этот ряд бесконечен, что для любого суперквантового компьютера найдётся задача, на которой он сломается. А между тем мы всё ещё топчемся где-то в районе P, и неизвестно, доберёмся ли когда-нибудь хотя бы до NP.
  В этом смысле проблемы открываются не только математические, но и философские. Луис Фернандо Ареан и об этом рассказал.
  Книга представляет собой обзор теории. Она должна представлять собой толстый том, но за такое чтение я совсем не стал бы браться, так что всё нормально.

  Снимаю шляпу перед Скоттом Ааронсоном. Он всё это понимает в деталях и даже составил список классов задач в соответствии с их сложностью -- Зоопарк сложностей. В нём более 400 зверей.

  Неожиданно почувствовал на пальцах, что такое доказательство с нулевым разглашением. Прежде понимал только теоретически. Может быть, это оттого, что Луис Фернандо Ареан заменил всем надоевших Алису и Боба Ахиллом с Брисеидой :)

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

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

  Дело за малым: построить машину времени. Говорят, на московском заводе Рено будут строить какие-то импортозамещённые автомобили. Лучше бы наладили производство машин времени :)

  Да, теория сложности слишком для меня сложна. В этой жизни я её точно не постигну.
  Но при случае прочитаю о ней что-нибудь ещё :)

  15

  216