Введение
Тип редукции Тьюринга
В теории вычислимости и теории вычислительной сложности редукция "многие к одному" (также называемая редукцией отображением) — это редукция, которая преобразует экземпляры одной задачи принятия решения (принадлежит ли экземпляр языку) в экземпляры другой задачи принятия решения (принадлежит ли экземпляр языку) с помощью вычислимой функции. Редуцированный экземпляр принадлежит языку тогда и только тогда, когда исходный экземпляр принадлежит его языку. Таким образом, если мы можем решить, принадлежат ли экземпляры языку , мы можем решить, принадлежат ли экземпляры языку , применив редукцию и решив для . Следовательно, редукции могут быть использованы для измерения относительной вычислительной сложности двух задач. Говорят, что редуцируется к , если, простыми словами, по крайней мере настолько же сложна для решения, как . Это означает, что любой алгоритм, решающий , также может быть использован как часть (в противном случае относительно простой) программы, решающей . Редукции "многие к одному" являются частным случаем и более сильной формой редукций Тьюринга. Позже Норман Шапиро использовал ту же концепцию в 1956 году под названием сильная редуцируемость.
In computability theory and computational complexity theory, a many one reduction (also called mapping reduction) is a reduction that converts instances of one decision problem (whether an instance is in ) to another decision problem (whether an instance is in ) using a computable function. The reduced instance is in the language if and only if the initial instance is in its language Thus if we can decide whether instances are in the language , we can decide whether instances are in its language by applying the reduction and solving for Thus, reductions can be used to measure the relative computational difficulty of two problems. It is said that reduces to if, in layman's terms is at least as hard to solve as This means that any algorithm that solves can also be used as part of a (otherwise relatively simple) program that solves
Many one reductions are a special case and stronger form of Turing reductions. Later Norman Shapiro used the same concept in 1956 under the name strong reducibility.
Много-одно полнота (m-полная)
Множество называется полным по Тьюрингу, или просто m-полным, если оно рекурсивно перечислимо и каждое рекурсивно перечислимое множество m-приводимо к нему.
Степень
Отношение действительно является отношением эквивалентности, его классы эквивалентности называются m-степенями и образуют частично упорядоченное множество с порядком, индуцированным .
Уменьшение карпа
Многочленное по времени сведение от задачи А к задаче В (обе задачи, как правило, должны быть задачами принятия решений) — это алгоритм, работающий за полиномиальное время, для преобразования входных данных задачи А во входные данные задачи В таким образом, что преобразованная задача имеет тот же результат, что и исходная задача. Экземпляр x задачи А можно решить, применив это сведение для получения экземпляра y задачи В, передав y на вход алгоритму для задачи В и вернув его результат. Сведения многочленного времени также могут быть известны как полиномиальные преобразования или сведение Карпа, названное в честь Ричарда Карпа. Такое сведение обозначается ≤m или ≼m.