Un problema se dice que es fuertemente NP-completo si sigue siéndolo incluso cuando todos sus parámetros numéricos están acotados por un polinomio en función de la longitud de la entrada.
Los parámetros numéricos de un problema normalmente se dan en la notación binaria, por lo que un problema de tamaño de entrada n pueden contener parámetros cuyo tamaño es exponencial en n. Si se redefine el problema para tener los parámetros dados en notación unaria, entonces los parámetros deben ser acotados por el tamaño de entrada.
Por lo tanto, la fuerte NP-completitud o NP-dureza también se pueden definir como NP-completitud o NP-dureza de la versión unaria del problema.
Mientras que los problemas débilmente NP-completos pueden admitir soluciones eficientes en la práctica siempre que sus entradas son de magnitud relativamente pequeña, los problemas fuertemente NP-completos no admiten soluciones eficientes en estos casos.
[3] Algunos problemas fuertemente NP-completos pueden ser fáciles de resolver, pero en la práctica es más probable encontrarse con casos difíciles.