Waktu semu-polinomial

Dalam teori kompleksitas komputasional, algoritma numerik berjalan dalam waktu semu-polinomial jika waktu operasinya adalah polinomial dari nilai numerik data yang dimasukkan (bilangan bulat terbesar yang ada dalam data tersebut) — dan tidak harus dalam panjang dari data yang dimasukkan (jumlah bit yang dibutuhkan untuk mewakili panjangnya), yang merupakan kasus untuk algoritma waktu polinomial.

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

Masalah kelengkapan-NP dengan algoritma 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 algoritma waktu semu-polinomial kecuali P=NP. Jenis kekerasan NP yang kuat/lemah didefinisikan secara analog.

 Referensi 
 Sumber 
 M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman and Company, 1979.

Kategori:Analisis algoritme
Kategori:Kelas kompleksitas
Kategori:Teori kompleksitas komputasi
Kategori:Algoritme waktu semu-polinomial