Cuando dice:
"Primero mostramos que CONTRATAR ∈ NP. Para esto, definimos un certificado para una instancia
(A, T, C, k) como un conjunto de aplicantes, definido mediante un arreglo de bits de tamaño n, donde
el i-ésimo bit del arreglo es 1 si el aplicante ai pertenece al conjunto, y 0 en otro caso."
no entiendo a qué conjunto se refiere. C se supone que es un conjunto de subconjuntos y que todos los ai aparecen ahí, o sea que serían todos unos? No le encuentro mucho sentido
hola Franco,
se refiere al "conjunto de aplicantes" que la solución propone como certificado. como el certificado debe ser un arreglo de bits, la forma en la que la solución representa ese conjunto con un arreglo de bits, es "encendiendo" las posiciones del arreglo que corresponden a los elementos que pertenecen al conjunto y dejando "apagadas" las posiciones de los que no. entonces, si el certificado es el conjunto de aplicantes {a_2,a_5} su representación como arreglo de bits sería [0,1,0,0,1,0].
saludos!
J