Введение

Проблема, которую может решить компьютер. В теоретической информатике вычислительная проблема — это проблема, которая может быть решена алгоритмом. Например, проблема факторизации:

"Для заданного положительного целого числа n найти нетривиальный простой делитель n."

является вычислительной проблемой. Вычислительную проблему можно рассматривать как множество экземпляров или случаев вместе с, возможно, пустым множеством решений для каждого экземпляра/случая. Например, в задаче факторизации экземплярами являются целые числа n, а решениями — простые числа p, являющиеся нетривиальными простыми делителями n.

Вычислительные проблемы — один из основных объектов изучения в теоретической информатике. Область теории вычислительной сложности пытается определить количество ресурсов (вычислительную сложность), необходимых для решения данной проблемы, и объяснить, почему некоторые проблемы являются неразрешимыми или невычислимыми. Вычислительные проблемы относятся к классам сложности, которые в широком смысле определяют ресурсы (например, время, пространство/память, энергия, глубина схемы), необходимые для их вычисления (решения) с помощью различных абстрактных машин. Например, классы сложности:

P — проблемы, требующие полиномиального времени для детерминированных классических машин;
BPP — проблемы, требующие полиномиального времени для вероятностных классических машин (например, компьютеров с генераторами случайных чисел);
BQP — проблемы, требующие полиномиального времени для вероятностных квантовых машин.

И экземпляры, и решения представлены двоичными строками, то есть элементами {0, 1}*. Например, натуральные числа обычно представляются в виде двоичных строк с использованием двоичного кодирования. Это важно, поскольку сложность выражается как функция длины входного представления.

Проблема решения

Проблема принятия решения — это вычислительная задача, для каждого экземпляра которой ответ может быть только «да» или «нет». Примером проблемы принятия решения является проверка на простоту:

«Для заданного положительного целого числа n определить, является ли n простым числом». Проблема принятия решения обычно представляется как множество всех экземпляров, для которых ответ «да». Например, проверка на простоту может быть представлена в виде бесконечного множества L = {2, 3, 5, 7, 11, …}.

Проблема поиска

В задаче поиска ответы могут быть произвольными строками. Например, факторизация – это задача поиска, где экземплярами являются (строковые представления) положительных целых чисел, а решениями – (строковые представления) наборов простых чисел. Задача поиска представляется как отношение, состоящее из всех пар «экземпляр-решение», называемое отношением поиска. Например, факторизацию можно представить как отношение

R = {(4, 2), (6, 2), (6, 3), (8, 2), (9, 3), (10, 2), (10, 5)}

которое состоит из всех пар чисел (n, p), где p является простым множителем n.

Проблема счисления

Задача подсчёта требует определения количества решений для заданной задачи поиска. Например, задача подсчёта, связанная с факторизацией, формулируется следующим образом:

"Для заданного положительного целого числа n подсчитайте количество нетривиальных простых множителей n."

Задача подсчёта может быть представлена функцией f, отображающей {0, 1}* в неотрицательные целые числа. Для отношения поиска R, задача подсчёта, связанная с R, определяется функцией

fR(x) = |{y: R(x, y)}|.

Проблема оптимизации

Проблема оптимизации заключается в поиске "наилучшего" решения среди всех возможных решений задачи поиска. Одним из примеров является задача о максимальном независимом множестве: "Для заданного графа G найти независимое множество G максимального размера". Задачи оптимизации представляются целевой функцией и ограничениями.

Проблема функции

В функциональной задаче для каждого входа ожидается единственный выход (полная функция), но этот выход сложнее, чем в задаче принятия решения, то есть он не ограничивается ответами "да" или "нет". Одним из самых известных примеров является задача коммивояжера:

"Дан список городов и расстояния между каждой парой городов. Необходимо найти кратчайший возможный маршрут, который посещает каждый город ровно один раз и возвращается в исходный город." Это NP-трудная задача в области комбинаторной оптимизации, имеющая важное значение в исследовании операций и теоретической информатике.