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