Содержание
7 отношения: Класс сложности, Сведение по Куку, Сведение по Карпу, Машина Тьюринга, Вычислительная сложность, Вычислимая функция, Вычисления с оракулом.
Класс сложности
В теории алгоритмов классами сложности называются множества вычислительных задач, примерно одинаковых по сложности вычисления.
Посмотреть Сведение (теория сложности вычислений) и Класс сложности
Сведение по Куку
В теории сложности вычислений сведение задачи R_1 к R_2 по Куку — это полиномиальный по времени алгоритм (другими словами, машина Тьюринга с полиномиальным временем работы), решающий задачу R_1 при условии, что функция, находящая решение задачи R_2, ему дана в качестве оракула, то есть обращение к ней занимает всего один шаг.
Посмотреть Сведение (теория сложности вычислений) и Сведение по Куку
Сведение по Карпу
Любой язык L_1 называется сводимым по Карпу к языку L_2, если существует функция F\colon \Sigma^* \mapsto \Sigma^*, вычисляемая за полиномиальное время, где F(x) принадлежит L_2 в том случае, если x принадлежит L_1.
Посмотреть Сведение (теория сложности вычислений) и Сведение по Карпу
Машина Тьюринга
Художественное представление машины Тьюринга Маши́на Тью́ринга (МТ) — абстрактный исполнитель (абстрактная вычислительная машина).
Посмотреть Сведение (теория сложности вычислений) и Машина Тьюринга
Вычислительная сложность
Вычисли́тельная сло́жность — понятие в информатике и теории алгоритмов, обозначающее функцию зависимости объёма работы, которая выполняется некоторым алгоритмом, от размера входных данных.
Посмотреть Сведение (теория сложности вычислений) и Вычислительная сложность
Вычислимая функция
Вычислимые функции — это множество функций вида, f\colon N \to N, которые могут быть реализованы на машине Тьюринга.
Посмотреть Сведение (теория сложности вычислений) и Вычислимая функция
Вычисления с оракулом
В теории вычислений и теории сложности машиной с оракулом называют абстрактную машину, предназначенную для решения какой-либо проблемы разрешимости.
Посмотреть Сведение (теория сложности вычислений) и Вычисления с оракулом