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 (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 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.

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.