Луис Фернандо Ареан — об авторе

Предложить изменения

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