La réduction polynomiale de plusieurs à une fois peut-elle être effectuée à une instance de problème spécifique?

Question

disons que je réduisez le problème $ a \ in l $ to $ b \ in k $ , avec une fonction $ f: \ sigma ^ {*} \ rightarrow \ gamma ^ {*} $ tel que w $ w \ dans l \ leftrightarrow f (w) \ in k $ . Je sais si je veux résoudre $ a $ , donné un algorithme de temps polynomial pour $ B $ , i il suffit de transformer $ a $ à $ b $ et résoudre $ B $ . Donc, on peut penser comme:

La réduction doit être effectuée à partir d'une instance arbitraire de $ a $ à une instance légale de $ B $

Ma question est que dois-je réduire à instance arbitraire de $ B $ ou certains instance de $ B $ ? C'est à dire. La réduction de TQBNF à la géographie généralisée est effectuée à une instance de graphique valide, mais il existe de nombreuses autres cas de géographie généralisées.

Answer 1

Le mappage ne doit pas nécessairement être sujectif (sur) ni injectif (un à un).En fait, tout problème qui peut être résolu en temps polynomial peut être un temps polynomial de plusieurs-un réduit à tout problème qui comporte au moins une instance d'acceptation et au moins une instance de rejet: résolvez simplement le problème d'origine en temps polynomial, puis renvoyez l'acceptation.instance si le problème initial était une instance d'acceptation, ou l'instance de rejet si le problème initial était une instance de rejet.

Cela dit, le La conjecture Berman-Hartmanis stipule que tous NP-complets les problèmes sont temps polynomial isomorphes , ce qui signifie qu'il y a un bijectif bijectif temps polynomial-time de plusieurs-une réduction entre eux avec un temps polynomialinverse.Il s'agit actuellement d'une conjecture non prouvée et ne fait référence que aux problèmes complets NP.