Вычислительная задача

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

«Давно положительное целое число 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, представляет собой функцию

ж _р (х) знак равно |{ у : р ( Икс , у ) }|.

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

Задача оптимизации требует найти «наилучшее возможное» решение среди множества всех возможных решений задачи поиска. Одним из примеров является задача о максимальном независимом множестве :

«Давно задан граф G , найдите независимое множество G максимального размера».

Задачи оптимизации представлены их целевой функцией и ограничениями.

Функциональная проблема

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

«Учитывая список городов и расстояния между каждой парой городов, найдите кратчайший возможный маршрут, который посещает каждый город ровно один раз и возвращается в исходный город».

Это NP-сложная задача комбинаторной оптимизации , важная в исследовании операций и теоретической информатике .

Проблема с обещанием

Основная статья: Проблема с обещаниями

В теории сложности вычислений обычно неявно предполагается, что любая строка в {0, 1} ^* представляет собой пример рассматриваемой вычислительной задачи. Однако иногда не все строки {0, 1} ^* представляют действительные экземпляры, и указывается правильное подмножество {0, 1} ^* как набор «действительных экземпляров». Вычислительные задачи такого типа называются проблемами обещаний .

Ниже приведен пример проблемы обещания (решения):

«Давно задан граф G , определите, каждое ли независимое множество в G имеет размер не более 5 или G имеет независимое множество размером не менее 10».

Здесь допустимыми экземплярами являются те графы, максимальный размер независимого набора которых составляет не более 5 или не менее 10.

Проблемы обещания решения обычно представляются как пары непересекающихся подмножеств ( L _да , L _нет ) из {0, 1} ^* . Допустимыми экземплярами являются экземпляры из L _yes ∪ L _no . Lyes _— и Lno _{соответственно} представляют собой случаи, ответ которых и нет да .

Проблемы обещаний играют важную роль в нескольких областях вычислительной сложности , включая сложность аппроксимации , проверку свойств и системы интерактивных доказательств .

См. также

• Латеральные вычисления , альтернативные подходы к решению задач вычислительным путем.
• Модель вычислений
• Трансвычислительная проблема

Ссылки

• Даже Шимон ; Селман, Алан Л .; Якоби, Яков (1984), «Сложность проблем обещаний с приложениями к криптографии с открытым ключом», Information and Control , 61 (2): 159–173, doi : 10.1016/S0019-9958(84)80056-X .
• Гольдрайх, Одед (2008), Вычислительная сложность: концептуальная перспектива , Cambridge University Press , ISBN  978-0-521-88473-0 .
• Гольдрейх, Одед ; Вигдерсон, Ави (2008), «IV.20 Вычислительная сложность», Гауэрс, Тимоти ; Барроу-Грин, июнь; Лидер, Имре (ред.), Princeton Companion to Mathematics , Princeton University Press, стр. 575–604, ISBN.  978-0-691-11880-2 .