Waktu semu-polinomial

Masalah kelengkapan-NP dengan algoritme waktu semu-polinomial diketahui disebut sebagai kelengkapan-NP yang lemah. Masalah kelengkapan-NP baru bisa disebut kelengkapan-NP yang kuat jika terbukti tidak dapat diselesaikan dengan algoritme waktu semu-polinomial kecuali P=NP. Jenis kekerasan NP yang kuat/lemah didefinisikan secara analog.