Calcolabilità e complessità: Domanda frequente

Quest'anno il prof ha fatto una domanda ricorrente:

Perchè se per definizione noi diciamo che un problema L1 è NP-hard se dato un L appartenente a NP, L <=p L1, poi quando facciamo la riduzione usiamo un solo problema?

Allora per prima cosa il prof intendeva questo, perchè per dimostrare che un problema è NP-hard non usiamo un generico linguaggio in NP ma lo riduciamo a un preciso linguaggio? Per esempio, per dimostrare che IS è NP-hard abbiamo usato la riduzione da SAT a IS.

Questo si può fare in quanto esiste un teorema:

Se L € NP-hard e L <=p L' => L' € NP-hard.
per ogni L'' € NP, L'' <=p L esiste f € P che trasforma L'' in L. Inoltre esiste una f' € P che trasforma L a L'. Quindi f ° f' è ancora polinomiale e mappa istanze di L'' in istanze di L', quindi f°f' è una trasformazione da L'' a L'.
Se L € NP-hard ed L <=p L' ed L' € NP => L' è NP-Complete.

Ora vi scrivo a parole cosa significa, noi abbiamo un problema L che è NP-hard, e due problemi L' e L'' tali per cui, L'' <= L <= L' ora il nostro scopo è quello di dimostrare che L'' <= L. Questo teorema lo dimostra così, L'' si riduce a L con una funzione f che è polinomiale, L si riduce a L' con un'altra funzione f' che è polinomiale, quindi L'' si riduce a L' con una funzione f°f' (f composizione f') che è ancora polinomiale. P.S. Questo è il link di wikipedia in cui spiega cos'è una composizione. Clicca qui
_________________
Quando la massa vede in te un Pazzo e folli le cose che dici, folli le cose che pensi, folli le cose che fai, allora sorridi e guardandoti allo specchio inchinati: sei davanti a un Genio.
Perchè coloro che sono abbastanza folli da pensare di cambiare il mondo, sono quelli che poi lo fanno...