Dalam teori kompleksitas komputasi, pengurangan waktu polinomial adalah metode untuk memecahkan satu masalah menggunakanlain. Pengurangan waktu polinomial sering digunakan dalam teori kompleksitas untuk mendefinisikan kelas kompleksitas dan menyelesaikan masalah untuk kelas tersebut. …
Apa yang dimaksud dengan waktu polinomial?
Suatu algoritma dikatakan polinomial waktu jika waktu berjalannya dibatasi oleh ekspresi polinomial dalam ukuran input untuk algoritma, yaitu, T(n)=O(nk) untuk beberapa konstanta positif k.
Bagaimana Anda tahu jika sesuatu adalah waktu polinomial?
3 Jawaban. Suatu algoritma adalah polinomial (memiliki waktu berjalan polinomial) jika untuk beberapa k, C>0, waktu berjalannya pada input berukuran n paling banyak adalah Cnk. Secara ekuivalen, suatu algoritma adalah polinomial jika untuk beberapa k>0, waktu berjalannya pada input berukuran n adalah O(nk).
Apa yang terjadi jika pengurangan diperbolehkan dalam waktu eksponensial?
Jika pengurangan diperbolehkan waktu eksponensial, maka itu dapat sepenuhnya menyelesaikan masalah asli dan menghasilkan turunan sepele dari masalah target Ini berarti setiap masalah di NP dapat direduksi ke setiap masalah lain dengan jenis pengurangan seperti itu, jadi setiap masalah di NP adalah NP-lengkap untuk pengurangan waktu eksponensial.
Apa yang dimaksud dengan algoritma eksponensial?
Suatu algoritma dikatakan waktu eksponensial, jika T(n) dibatasi oleh 2poly( ) , di mana poli(n) adalah beberapa polinomial dalam n. Secara lebih formal, suatu algoritma adalah waktu eksponensial jika T(n) dibatasi oleh O(2nk) untuk beberapa konstanta k. Ref:Wiki.
