Сведение
Sign in to savetransformation of one computational problem to another, used to show that the second problem is as difficult as the first
In the Vinony graph
Vinony's link graph records 94 inbound references to Сведение, and connects out to time complexity, polynomial-time reduction and International Standard Book Number.
It is catalogued under the topic Reduction (complexity).
Vinony links it to 19 Wikipedia language editions.
Wikidata facts
Show 3 more facts
- facet of
- problem solving
- Stack Exchange tag
- cstheory.stackexchange.com/tags/reductions
- maintained by WikiProject
- WikiProject Mathematics
Sources (1)
via Wikidata · CC0
Article · Русский
Сведе́ние в теории сложности вычислений — преобразование одной задачи к другой. В общем случае, для алгоритма, преобразующего экземпляры задачи в экземпляры задачи , которые имеют тот же ответ («да» или «нет»), говорят, что сводится к , таким образом, сводимость — это отношение между двумя задачами. С помощью такой связи могут быть доказаны вычислимость задачи или её принадлежность тому или иному классу сложности. Некоторые виды сведений: сведение по Куку, сведение по Карпу, , . Сведение по Тьюрингу — наиболее общая форма сведения: некоторый алгоритм (вычислимый на машине Тьюринга) может быть вызван любое количество раз, при этом каждый вызов будет считаться за один шаг алгоритма; для формального определения сводимости по Тьюрингу используется понятие тьюринг-машины с оракулом.
Abstract from DBpedia / Wikipedia · CC BY-SA