Whether under these types of reductions the definition of NP-complete changes is still an open problem.
Întrebarea dacă în aceste tipuri de reduceri definiția NP-completitudinii se modifică este încă o problemă deschisă.