Книга: Золотой билет
За границей королевства
Мы с вами лишь слегка коснулись огромного множества NP-задач, которые невозможно решить за разумное время. Вам, наверно, кажется, что проблема равенства P и NP интересна только жителям воображаемого Королевства да еще узкому кругу математиков, связанных с вычислительной техникой. Чтобы развеять это впечатление, рассмотрим еще несколько задач из NP, не имеющих эффективных алгоритмов решения (и принадлежащих, кстати, к разным областям науки).
Оглавление статьи/книги