Quiz ADA P vs NP

Berdasarkan Penjelasan sifat-siaft problem P dan NP sebelumnya dari sesi sebelumnya, Manakah dari sifat-sifat berikut yang tidak termasuk dari sifat problem NP?

• Pengujian kebenaran output problem NP akan berjalan dengan kompleksitas waktu polinomial.

• Karena memiliki sifat pembuktian kebenaran yang sama, Problem P juga termasuk ke dalam Kelas Problem NP.

• Problem NP dapat dicari nilai optimalnya dalam batas kompleksitas waktu eksponensial.

• Problem NP dapat dicari nilai optimalnya dalam batas kompleksitas waktu polinomial.

Dalam tingkatan kelas problem NP, terdapat beberapa problem dengan inti pokok permasalahan yang sama sehingga memiliki peluang untuk diselesaikan. Problem tersebut disebut sebagai?

• NP-Complete

• NP-hard

• NP-Easy

• P Problem

Diantara problem yang telah di-telusuri oleh peneliti, beberapa problem berikut ini memiliki kelas kompleksitas problem P. Pilihlah problem tersebut!

• Sorting

• Perkalian Matriks

• Catur

• Sudoku

Jika ditemukan algoritma polinomial untuk menyelesaikan salah satu masalah NP-Complete, maka yang terjadi adalah:

• Tidak ada perubahan dalam dunia komputasi.

• Semua masalah dalam P akan menjadi lebih mudah.

• Semua masalah dalam NP dapat diselesaikan dalam waktu polinomial.

• Semua masalah dalam P akan menjadi NP-Hard.

Masalah NP-HARD memiliki karakteristik utama yang membedakan dari Masalah NP umumnya adalah:

• Masalah yang hanya bisa diverifikasi dalam waktu eksponensial

• Masalah yang bisa diselesaikan dan diverifikasi dalam waktu linear

• Masalah yang bisa diverifikasi dalam waktu polinomial, tapi belum tentu bisa diselesaikan dalam waktu polinomial

• Masalah yang tidak bisa diverifikasi sama sekali

Manakah dari pernyataan berikut yang benar mengenai masalah NP-Complete?

• Semua masalah dalam NP-Complete dapat diselesaikan dalam waktu polinomial.

• Jika satu masalah NP-Complete dapat diselesaikan dalam waktu polinomial, maka semua masalah dalam NP dapat diselesaikan dalam waktu polinomial.

• Masalah NP-Complete selalu lebih sulit daripada masalah di kelas P.

• Tidak ada hubungan antara NP-Complete dan NP.

Manakah pernyataan yang benar mengenai kelas masalah P dan NP?

• Semua masalah dalam kelas P juga termasuk dalam kelas NP.

• Semua masalah dalam kelas NP juga ada dalam kelas P.

• Masalah dalam kelas P tidak dapat diverifikasi dengan cepat.

• Baik kelas P dan NP adalah dua kelas masalah yang tidak memiliki hubungan satu dengan yang lainnya.

Pilihlah contoh dari kasus dalam kelas NP!

• Password Hacking

• Job Scheduler

• Travelling Salesman

• Chess Bot

Seorang pengembang aplikasi navigasi sedang mencoba untuk mengembangkan algoritma yang dapat menemukan rute terpendek bagi pengguna di sebuah kota besar yang terdiri dari banyak titik lokasi. Setiap titik lokasi di kota tersebut terhubung dengan jalan-jalan yang memiliki panjang berbeda-beda. Pengguna ingin mengetahui rute terpendek yang menghubungkan dua lokasi tertentu, yang dapat dipilih secara acak. Apabila pengembang aplikasi menggunakan algoritma Greedy Dijkstra, problem tersebut termasuk ke dalam kelas:

• Non-Deterministic

  Polynomial

• Polynomial

Misalkan kamu sedang bermain Sudoku, mengapa permainan ini termasuk dalam masalah NP?

• Karena semua permainan logika termasuk kelas NP.

• Karena solusi dapat ditemukan dengan algoritma deterministik dalam waktu polinomial.

• Karena solusinya dapat diverifikasi dengan cepat, meskipun menemukannya sulit.

• Karena tidak ada solusi yang dapat ditemukan atau diverifikasi dalam waktu polinomial.