Закон Мура
Мы живем в замечательном мире. Вычислительная мощность компьютеров удваивается каждые полтора года с 1971 года. Все предрекают скорое окончание этой замечательной эпохи, но пока так называемый Закон Мура продолжает выполняться. Правда, в зависимости от момента времени мы понимаем его по-разному. Так или иначе задачи, которые сейчас требует месяц расчетов, через три года будут считаться за неделю, а через шесть лет – всего за два дня. И с каждым годом появляется возможность посчитать то, что раньше считалось невозможным.
Казалось бы, остается только ждать и смотреть в светлое будущее. Но есть целый класс задач, быстрое решение которых даже несмотря на закон Мура остаётся в несбыточных мечтах. Это задачи, сложность которых увеличивается экспоненциально с увеличением количества параметров. Отсутствие решения для таких задач может быть даже полезно. Приведем несколько примеров.