Nem. Az NP-teljesseg egy tok konkret, bizonyithato fogalom. Az mar mas kerdes, hogy P==NP vagy P!=NP. Attol meg maga a problema NP-teljes marad.
Egy problema bekategorizalasan (P, NP-hard, PSpace stb.) nem valtoztat az, hogy ket halmazrol kozben kiderul, hogy egyenloek.