Cтраница 3
Большинство дискретных и комбинаторных проблем, вообще говоря, допускает решение с помощью некоторого процесса перебора. Однако число шагов переборного метода растет экспоненциально в зависимости от размерности задачи. Для некоторых проблем этого типа удается построить эффективные ( существенно менее трудоемкие, чем полный перебор вариантов) методы решения. К сожалению, число таких задач невелико. Для отличия удобных и неудобных задач на терминологическом уровне вводятся специальные понятия. Так задачу, для которой существует алгоритм решения существенно более экономичный, чем перебор экспоненциального числа вариантов, называют алгоритмически разрешимой. Если же такого алгоритма найти невозможно, то задачу называют алгоритмически неразрешимой. Стало общепринятым считать переборную задачу решаемой эффективно, если имеется алгоритм, решающий ее за время, ограниченное полиномом от размерности задачи. [31]