Я изучаю вычислимость и сложность, и у меня возникли сомнения. Функция, которая сводит проблему к другой, является вычислимой по Тьюрингу. Мне было интересно, является ли это даже взаимно-однозначной функцией (соответствием), поскольку, глядя, например, на сокращение Vertex-Cover -> Independent Set, я не могу увидеть, где экземпляр одной проблемы не соответствует другому экземпляру другой.
Спасибо
Нет, прямой переписки нет. Если свести задачу A к задаче B, например, за полиномиальное время (A ‹=_pol B), это означает, что можно решить задачу A с помощью решения задачи B. Но возможно, что есть вход для проблему B вы не можете решить с помощью решения A. Также функция сокращения может отображать несколько входных данных для проблемы A в один вход для проблемы B.
Возьмем, к примеру, сведение Clique(G,k) к SubgraphIsomorphism(G,H): Clique ‹=_pol SubgraphIsomorphism. Клика — это всего лишь специальный подграф H, который можно построить полиномиально по k за время. Но умение решать Clique(G,k) не поможет вам найти произвольные подграфы H в G. Таким образом, не все входные данные для SubgraphIsomorphism соответствуют входным данным для Clique. Эта редукция просто показывает, что SubgraphIsomorphism по крайней мере так же сложен, как Clique.
