Saya menemukan masalah P vs NP beberapa waktu lalu dan saya baru saja bekerja pada masalah jumlah subset. Saya telah membaca artikel Wikipedia tentang masalah Subset Sum serta pertanyaan Algoritma Subset Sum
Saya telah melihat masalah dan menemukan beberapa solusi tetapi sejauh ini mereka tampaknya NP, saya percaya saya dapat membuat algoritma yang cukup cepat dalam waktu NP.
Masalah saya adalah teori saya tidak bagus sehingga tidak banyak membantu saya untuk membicarakan Teorema Cook-Levin atau Mesin Turing Non-Deterministik.
Apa yang saya inginkan adalah penjelasan tentang jumlah subset pemrograman dinamis waktu semu-polinomial yang ada di Wikipedia.
Saya telah membacanya dan saya percaya saya mengerti konsep umum mengapa itu adalah NP bukan P (terkait dengan ukuran input daripada operasi dengan itu), tetapi saya tidak mengerti algoritma.
Saya akan sangat menghargai jika seseorang memberikan contoh dengan beberapa angka dan cara kerjanya. Itu akan banyak membantu saya karena itu akan:
- Berikan saya ide untuk meningkatkan algoritma masa depan saya
- Bantu saya memahami secara intuitif ketika suatu algoritma pseudo-polonmial bukan NP.
sumber
Jawaban:
Mengulangi komentar Kaveh sebagai jawaban:
Jika Anda mengikat ukuran nilai dalam input (mengikat jumlah bit untuk setiap nilai menjadi logaritmik dalam jumlah total bit input) maka masalahnya dapat diselesaikan dalam waktu polinomial menggunakan pemrograman dinamis. Jika tidak dibatasi, mereka dapat memiliki nilai yang besar secara eksponensial dan ukuran tabel untuk pemrograman dinamis akan eksponensial.
sumber