Riduzione polinomiale da Set cover a Vertex cover

[alvinlee881]

Salve a tutti, ho qualche dubbio relativo alla teoria della NP-completezza. Suppongo che chi legge sappia cosa sono i problemi di ci parlerò sotto, e conosca un pò di termini della teoria in questione. Se no, ditemelo che provo a riassumere
Sappiamo dimostrare che Vertex Cover (in seguito $V.C.$ ) si riduce polinomialmente a Set Cover ( in seguito $S.C.$), cioè $V.C<=S.C$Sappiamo inoltre che sono entrambi problemi NP-COMPLETI, cioè appartengono a NP e ogni altro problema di NP si può ridurre polinomialmente a loro. In particolare $V.C.$ è NP-COMPLETO. Ciò vuol dire che ogni altro problema $X in NP$, e quindi anche $S.C.$ (poichè appartiene a NP) si può ridurre polinomialmente a $V.C.$, cioè vale $S.C<=V.C$, e in definitiva $S.C=V.C$ , cioè sono equivalenti. Si può qinid concludere che tutti i problemi di NP-C sono eqivalenti. E' giusto? Se lo è, come si può dimostrare indiepndentemente dalla nozione di NP-completezza che $S.C.<=V.C$? Cioè coe si può trasfomare un'istanza di Set Cover in una di Vertex cover? il viceversa è facile, ma a me interessa questo. Ho fatto vari tentativi, ma nesusno mi convince. Chi conosce un pò di questa materia, potrebbe gentilmente darmi una mano?