Имеется 6 видов вычислительных проблем, с которыми вы можете столкнуться:
-
Экземпляры задач - Вычислительные проблемы(задачи) можно рассматривать как бесконечный набор пар: (экземпляр задачи, решение для данного экземпляра). Входной строкой для вычислительной проблемы является строка, описывающая экземпляр задачи. Выходная строка для вычислительной проблемы — описание решения для экземпляра задачи, описанного входной строкой. Например, проблема распознавания простоты числа: экземпляр задачи — число, для которого следует определить простое оно или нет, решение — строка «да», если это число простое и «нет» в противном случае. Теория сложности вычислений рассматривает только массовые задачи, т.е. требование о бесконечности набора экземпляров задач обязательно.