Waktu semu-polinomial

Secara umum, nilai numerik dari data yang dimasukkan termasuk eksponensial pada panjangnya, oleh karena itu algoritme waktu semu-polinomial tidak harus berjalan dalam waktu polinomial sesuai dengan panjang masukan.