Comprendre la définition de la réduction

Question

De Wikipedia :

  

Etant donné deux sous-ensembles A et B de N et un ensemble de fonctions F de N à N   qui est fermée par composition, A est appelé réductibles à B sous F   si $$      \ Existe f \ dans F \ mbox {. } \ Forall x \ in \ mathbb {N} \ mbox {. } X \ in A \ leftrightarrow f (x) \ in B $$ On écrit $$      A \ leq_ {F} $$ B Soit S un sous-ensemble de P (N) et = une réduction, alors S est appelé sous fermé = si $$      \ Forall s \ dans S \ mbox {. } \ Forall A \ in P (\ mathbb {N}) \ mbox {. } A \ leq s \ Rightarrow A \ in S $$ Un sous-ensemble A de N est appelé dur S   si $$      \ Forall s \ dans S \ mbox {. } S \ leq A $$ Un sous-ensemble A de N est appelé complet pour S si A est dur S et A est S.

Je suis en train de relier les définitions ci-dessus à ceux des problèmes: problème A peut être réduit à un problème B, un ensemble de problèmes sont NP-difficiles, un ensemble de problèmes sont NP-complets. Mais je ne sais pas comment raconter. Je pense qu'un lien me manque est de voir comment un sous-ensemble du problème peut être considéré comme un sous-ensemble de $ \ mathbb {N} $?

Answer 1

La définition que vous citez est très abstrait, mais les concepts que vous essayez de comprendre sont assez intuitive. Un problème $ A $ est NP-dur si vous pouvez résoudre tout problème dans NP utiliser. Cela signifie que tout $ B \ in NP $ peut être réduite à $ A $, à savoir il y a une fonction de polynomial $ f $ tel que $ x \ in B $ ssi $ f (x) \ in A $; de sorte que vous pouvez tester si $ x \ in B $ en calculant $ f (x) $ et de tester si celle-ci est en $ A $.

A problème est NP-complet si elle est à la fois dans le NP-dur et dans NP. Cela signifie qu'il est plus difficile parmi les problèmes NP. Un problème peut être NP-dur sans être dans NP, par exemple, le problème de l'arrêt.

Vous parlez des ensembles de problèmes comme appartenant à NP, mais c'est une erreur de frappe: les membres du NP sont des problèmes, sous la forme de sous-ensembles de l'ensemble des nombres naturels (ou de l'ensemble des chaînes binaires finies, ce qui est le même). Les sous-ensemble spécifie l'ensemble d'entrées pour lesquelles le problème a le OUI réponse.