If one defines the analogue to NP-complete with Turing reductions instead of many-one reductions, the resulting set of problems won't be smaller than NP-complete; it is an open question whether it will be any larger.
Dacă se definește conceptul analog NP-completitudinii cu reduceri Turing în loc de mai reduceri many-one, mulțimea de probleme rezultată nu va fi mai mică decât cea a problemelor NP-complete; este o întrebare deschisă însă dacă este mai mare.