Kompleksitas komputasional

Konsep dalam Ilmu Komputer

Pritesh Patel

Computer Scientist & Data Scientist for over 20 years

Kelas kompleksitas

Kelas Kompleksitas

Animasi yang menunjukkan seluruh ruang kompleksitas masalah

Gambar yang menunjukkan ruang masalah P

Kelas Kompleksitas -->	P (Waktu Polinomial)
Artinya	Dapat diselesaikan cepat dan efisien
Contoh	Mengurutkan daftar
Analogi	"Mengarsip dokumen secara alfabetis"
Inti	Ini "mudah" secara komputasional

¹ https://www.baeldung.com/cs/p-np-np-complete-np-hard

Gambar yang menunjukkan ruang masalah P dan NP

Kelas Kompleksitas -->	NP (Waktu Polinomial Nondeterministik)
Artinya	Solusi dapat diverifikasi; menemukan solusi baru itu sulit
Contoh	Memverifikasi solusi teka-teki Sudoku
Analogi	"Mencari dokumen spesifik dengan info yang kurang"
Inti	Verifikasi solusi itu "mudah", menemukan solusi baru itu sulit

¹ https://www.baeldung.com/cs/p-np-np-complete-np-hard

Gambar yang menunjukkan ruang masalah P, NP, dan NP-Complete

Kelas Kompleksitas -->	NP-Complete
Artinya	Tersulit di NP. Khusus karena mewakili semua masalah NP
Contoh	Masalah pedagang keliling (TSP)
Analogi	"Menyusun puzzle rumit: mudah diverifikasi, sulit dipecahkan"
Inti	Belum ada solusi efisien yang diketahui; jika ada, semua NP terpecahkan

¹ https://www.baeldung.com/cs/p-np-np-complete-np-hard

Gambar yang menunjukkan ruang masalah P, NP, NP-Complete, dan NP-Hard

Kelas Kompleksitas -->	NP-Hard
Artinya	Sesulit NP-Complete atau lebih sulit
Contoh	Penjadwalan optimal dengan ketergantungan kompleks dan tak terverifikasi
Analogi	"Menjadwalkan rapat optimal dengan banyak kendala dan tak cepat diverifikasi"
Inti	Mungkin tak praktis untuk diselesaikan

¹ https://www.baeldung.com/cs/p-np-np-complete-np-hard

Diagram yang menanyakan pertanyaan klasik: apakah P=NP?

Konsep dalam Ilmu Komputer