A redução polinomial de muitos-para-um pode ser feita para uma instância de problema específica?

Question

digamos que eu reduzo o problema $ a \ in l $ para $ b \ in k $ , com uma função $ f: \ sigma ^ {*} \ righttarrow \ gamma ^ {*} $ << / span> tal que $ w \ in l \ leftrightarrow f (w) \ in k $ . Eu sei se quero resolver $ a $ , dado algum algoritmo de tempo polinomial para $ B $ , i só tem que transformar $ a $ para $ B $ e resolver $ B $ . Por isso pode ser pensado como:

.

A redução deve ser feita a partir da instância arbitrária de $ a $ para uma instância legal de $ B $

Minha pergunta é, eu tenho que reduzir para arbitrário instância de $ b $ ou alguma instância de $ b $ ? Isto é A redução do TQBNF para geografia generalizada é feita para alguma instância de gráfico válida, mas existem muitos casos mais válidos da geografia generalizada.

Answer 1

O mapeamento não precisa ser superjetivo (sobre) nem injeccionista (um para um).De fato, qualquer problema que possa ser resolvido em tempo polinômico pode ser tempo polinomial muitos um um reduzido a qualquer problema que tenha pelo menos uma instância de aceitação e pelo menos uma instância de rejeição: basta resolver o problema original no tempo polinomial e, em seguida, devolver a aceitaçãoinstância se o problema original fosse uma instância de aceitação ou a instância de rejeição se o problema original fosse uma instância de rejeição.

Dito isto, o Conjecture Berman-Hartmanis afirma que todos np-completo Problemas são ISOMORPHIC , o que significa que existe um bijectivo tempo polinomial-tempo muitos - uma redução entre eles com um tempo polinomialinverso.Esta é atualmente uma conjectura não comprovada, e refere-se apenas a problemas completos de NP.