Waktu semu-polinomial

Dalam teori kompleksitas komputasional, algoritme numerik berjalan dalam waktu semu-polinomial jika waktu operasinya adalah polinomial dari nilai numerik data yang dimasukkan — dan tidak harus dalam panjang dari data yang dimasukkan, yang merupakan kasus untuk algoritme waktu 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. 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.