Сведение (теория сложности вычислений)

Сведение (теория сложности вычислений)
У этого термина существуют и другие значения, см. Сведение.

В теории сложности вычислений сведе́ние — преобразование одной задачи к другой. В общем случае, если у нас есть алгоритм, преобразующий экземпляры задачи P_1 в экземпляры задачи P_2, которые имеют тот же ответ (да/нет), то говорят, что P_1 сводится к P_2. Таким образом, сводимость — это отношение между двумя задачами. С помощью такой связи могут быть доказаны вычислимость задачи или ее принадлежность тому или иному классу сложности.

Некоторые виды сведений

Самым общим типом сведения является Сведение по Тьюрингу, оно же - Сведение по Куку. В данном случае некоторый алгоритм (вычислимый на машине Тьюринга) может быть вызван любое количество раз, при этом каждый вызов будет считаться за один шаг алгоритма. Для формального определения сводимости по Тьюрингу используется понятие Тьюринг-машины с оракулом.

Ссылки

Литература

  • Джон Хопкрофт, Раджив Мотвани, Джеффри Ульман Введение в теорию автоматов, языков и вычислений = Introduction to Automata Theory, Languages, and Computation. — М.: «Вильямс», 2002. — С. 528. — ISBN 0-201-44124-1

Wikimedia Foundation. 2010.

Игры ⚽ Поможем решить контрольную работу

Полезное


Смотреть что такое "Сведение (теория сложности вычислений)" в других словарях:

  • Теория сложности вычислений — В информатике, теория сложности вычислений является разделом теории вычислений, изучающим стоимость работы, требуемой для решения вычислительной проблемы. Стоимость обычно измеряется абстрактными понятиями времени и пространства, называемыми… …   Википедия

  • Сведение по Карпу — Любой язык программирования называется сводимым по Карпу к языку , если существует функция , вычисляемая за полиномиальное время, где F(x) принадлежит в том случае, если x принадлежит . Язык называется NP трудным, если к нему сводится любой язык… …   Википедия

  • Сведение по Куку — В теории сложности вычислений сведение задачи к по Куку это полиномиальный по времени алгоритм (другими словами, машина Тьюринга с полиномиальным временем работы), решающий задачу при условии, что функция, находящая решение задачи , ему дана в… …   Википедия

  • Сведение — цветов cовмещение цветоделённых изображений в фотографии, полиграфии, телевизионной аппаратуре. Сведение лучей цветных электронно лучевых трубок Сведение (теория сложности вычислений) Сведение (звукозапись) Сведение …   Википедия

  • Временная сложность алгоритма — Содержание 1 Временная и пространственная сложности 1.1 Асимптотическая сложность 1.2 Примеры …   Википедия

  • Вычислительная сложность — В информатике и теории алгоритмов вычислительная сложность алгоритма это функция, определяющая зависимость объёма работы, выполняемой некоторым алгоритмом, от размера входных данных. Раздел, изучающий вычислительную сложность, называется теорией… …   Википедия

  • Задача SAT — Задача выполнимости булевых формул (SAT или ВЫП) задача распознавания, важная для теории вычислительной сложности. Экземпляром задачи SAT является булева формула, состоящая только из имен переменных, скобок и операций (И), (ИЛИ) и (HE). Задача… …   Википедия

  • Задача ВЫП — Задача выполнимости булевых формул (SAT или ВЫП) задача распознавания, важная для теории вычислительной сложности. Экземпляром задачи SAT является булева формула, состоящая только из имен переменных, скобок и операций (И), (ИЛИ) и (HE). Задача… …   Википедия

  • Теорема Кука — Теорема Кука  Левина (также просто теорема Кука) утверждает, что за­да­ча о вы­пол­ни­мо­сти булевой формулы в КНФ (SAT) яв­ля­ет­ся NP пол­ной. Доказательство этой теоремы, по­лу­чен­ное Стивеном Куком в его фун­да­мен­та­ль­ной ра­бо­те в… …   Википедия

  • Кибернетика — I Кибернетика (от греч. kybernetike искусство управления, от kybernáo правлю рулём, управляю)         наука об управлении, связи и переработке информации (См. Информация).          Предмет кибернетики. Основным объектом исследования в К. являются …   Большая советская энциклопедия


Поделиться ссылкой на выделенное

Прямая ссылка:
… Нажмите правой клавишей мыши и выберите «Копировать ссылку»