Книга: Золотой билет

После Карпа

Работа Карпа послужила толчком к дальнейшему развитию информатики. NP-полные задачи множились, как грибы; профессора и аспиранты по всему миру брались за известные поисковые проблемы (а также находили новые) и доказывали их NP-полноту. В классическом труде 1979 года[3] приводится более трехсот основополагающих NP-полных задач. Число их неудержимо растет; NP-полные задачи возникают не только в информатике и математике, но и в физике, биологии, экономике и во многих других областях. Поиск по Академии Google выдает более 138000 научных статей об NP-полноте за период с 1972 по 2011 год, и в одном только 2011 году на эту тему было создано около 10000 работ. Вряд ли имеет смысл приводить здесь список всех NP-полных задач, однако мне хотелось бы дать вам представление о некоторых из них.

Оглавление книги