В теоретической информатике вычислительная задача — это проблема, которая может быть решена с помощью алгоритма . Например, задача факторинга
это вычислительная проблема. Вычислительную задачу можно рассматривать как набор случаев или случаев вместе с (возможно , пустым) набором решений для каждого экземпляра/случая. Например, в задаче факторизации экземплярами являются целые числа 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 .Lyes и Lno представляют собой случаи, ответ которых — да и нет соответственно .
Проблемы обещаний играют важную роль в нескольких областях вычислительной сложности , включая сложность аппроксимации , проверку свойств и системы интерактивных доказательств .