La comprensión de la definición de la reducción

Question

Wikipedia :

Dados dos subconjuntos A y B de N y un conjunto de funciones F de N a N que está cerrado en virtud de composición, A se llama reducible a B bajo F Si $$ \ Existe f \ in F \ mbox {. } \ Forall x \ in \ mathbb {N} \ mbox {. } X \ in A \ leftrightarrow f (x) \ in B $$ $$ Escribimos A \ leq_ {F} B $$ sea S un subconjunto de P (N) y = una reducción, entonces S se llama bajo cerrado = si $$ \ Forall s \ in S \ mbox {. } \ Forall A \ in P (\ mathbb {N}) \ mbox {. } A \ leq s \ Rightarrow A \ en S $$ Un subconjunto A de N se llama difícil para S Si $$ \ Forall s \ in S \ mbox {. } S \ leq A $$ Un subconjunto A de N se llama completa de S si A es difícil para S y A se encuentra en S.

Estoy tratando de relacionar las definiciones anteriores a las de los problemas: Un problema puede reducirse a un problema B, un conjunto de problemas son NP-duro, un conjunto de problemas son NP-completo. Pero no sé cómo relacionar. Creo que un enlace que me falta es ver como un subconjunto del problema puede ser visto como un subconjunto de $ \ mathbb {N} $?

Answer 1

La definición se está citando es muy abstracto, pero los conceptos que está tratando de entender son bastante intuitiva. Un problema $ A $ es NP-difícil si se puede resolver cualquier problema en NP usarlo. Esto significa que cualquier $ B \ en NP $ puede ser reducido a $ A $, es decir, hay alguna función polytime $ f $ tal que $ x \ in B $ si y sólo si $ f (x) \ in A $; por lo que se puede comprobar si $ x \ in B $ calculando $ f (x) $ y probar si éste se encuentra en $ A $.

Un problema es NP-completo si es tanto en NP-duro y en NP. Esto significa que es más difícil entre los problemas en NP. Un problema puede ser NP-duro sin estar en NP, por ejemplo, el problema de la parada.

Usted está mencionando conjuntos de problemas como perteneciente a NP, pero eso es un error de escritura: los miembros de NP problemas, bajo la apariencia de subconjuntos del conjunto de los números naturales (o del conjunto de cadenas binarias finitos, que es lo mismo). El subconjunto especifica el conjunto de entradas para las que el problema tiene la SI respuesta.