В теоретической информатике вычислительная задача — это задача, требующая решения в виде алгоритма . Например, задача факторизации
— это вычислительная задача, имеющая решение, поскольку существует множество известных алгоритмов факторизации целых чисел . Вычислительную задачу можно рассматривать как набор экземпляров или случаев вместе с , возможно, пустым, набором решений для каждого экземпляра/случая. Тогда возникает вопрос, существует ли алгоритм, который отображает экземпляры в решения. Например, в задаче факторизации экземплярами являются целые числа n , а решениями — простые числа p, которые являются нетривиальными простыми множителями n . Примером вычислительной задачи без решения является проблема остановки . Вычислительные задачи являются одним из основных объектов изучения в теоретической информатике.
Часто интересуются не только самим существованием алгоритма, но и тем, насколько эффективным может быть алгоритм. Область теории вычислительной сложности решает такие вопросы, определяя объем ресурсов ( вычислительную сложность ), необходимых для решения данной проблемы, и объясняя, почему некоторые проблемы неразрешимы или неразрешимы . Решаемые вычислительные проблемы относятся к классам сложности , которые в общих чертах определяют ресурсы (например, время, пространство/память, энергию, глубину схемы), необходимые для их вычисления (решения) с помощью различных абстрактных машин . Например, классы сложности
Оба экземпляра и решения представлены двоичными строками , а именно элементами {0, 1} * . [a] Например, натуральные числа обычно представляются в виде двоичных строк с использованием двоичного кодирования . Это важно, поскольку сложность выражается как функция длины входного представления.
Проблема принятия решения — это вычислительная проблема, где ответ для каждого случая — «да» или «нет». Примером проблемы принятия решения является проверка простоты :
Проблема принятия решения обычно представляется как множество всех случаев, для которых ответ да . Например, проверка простоты может быть представлена как бесконечное множество
В задаче поиска ответы могут быть произвольными строками. Например, факторизация — это задача поиска, где экземпляры — это (строковые представления) положительных целых чисел, а решения — это (строковые представления) наборов простых чисел.
Задача поиска представляется как отношение, состоящее из всех пар экземпляр-решение, называемое отношением поиска . Например, факторизация может быть представлена как отношение
которые состоят из всех пар чисел ( n , p ), где p — простой множитель n .
Задача подсчета требует количества решений для данной задачи поиска. Например, задача подсчета, связанная с факторизацией, это
Задача подсчета может быть представлена функцией f от {0, 1} * до неотрицательных целых чисел. Для поискового отношения R задача подсчета, связанная с R, является функцией
Задача оптимизации требует найти «наилучшее возможное» решение среди множества всех возможных решений задачи поиска. Одним из примеров является задача максимального независимого множества :
Задачи оптимизации представлены их целевой функцией и ограничениями.
В функциональной задаче ожидается один выход (полной функции ) для каждого входа, но выход более сложен, чем в задаче принятия решения , то есть это не просто «да» или «нет». Одним из самых известных примеров является задача коммивояжера :
Это NP-трудная задача комбинаторной оптимизации , важная для исследования операций и теоретической информатики .
В теории вычислительной сложности обычно неявно предполагается, что любая строка в {0, 1} * представляет экземпляр рассматриваемой вычислительной проблемы. Однако иногда не все строки {0, 1} * представляют допустимые экземпляры, и указывается надлежащее подмножество {0, 1} * как набор «допустимых экземпляров». Вычислительные задачи такого типа называются задачами обещаний .
Ниже приведен пример проблемы обещания (решения):
Здесь допустимыми экземплярами являются те графы, максимальный размер независимого множества которых составляет либо не более 5, либо не менее 10.
Проблемы обещания решения обычно представляются в виде пар непересекающихся подмножеств ( L yes , L no ) из {0, 1} * . Допустимыми являются экземпляры в L yes ∪ L no . L yes и L no представляют собой экземпляры, ответом на которые является yes и no соответственно.
Проблемы обещаний играют важную роль в нескольких областях вычислительной сложности , включая сложность аппроксимации , тестирование свойств и интерактивные системы доказательств .