Subbab 4.2 Pengantar Teori Kompleksitas

Soal pertama dari ketiga soal tersebut terdengar mudah, dan memang demikian. Anda cukup memeriksa bilangan-bilangan dalam himpunan itu satu per satu untuk mengetahui apakah salah satunya adalah \(83,172\text{.}\) Anda dapat berhenti begitu menemukan bilangan ini dan melaporkan bahwa jawabannya ya. Jika jawaban yang Anda berikan adalah tidak, Anda harus sudah membaca setiap bilangan dalam daftar. Dalam kedua keadaan itu, Anda berhenti dengan jawaban yang benar setelah melakukan paling banyak \(10,000\) pengujian, dan netbook yang paling sederhana sekalipun dapat melakukannya dalam sekejap. Bahkan jika daftar itu diperbesar menjadi \(1,000,000\) bilangan bulat yang semuanya paling besar satu miliar, Anda masih dapat menyelesaikannya dengan mudah. Secara lebih umum, jika Anda diberi sebuah himpunan \(S\) yang terdiri atas \(n\) bilangan dan sebuah bilangan bulat \(x\text{,}\) dengan pertanyaan “Apakah \(x\) merupakan anggota \(S\text{?}\)”, Anda dapat menjawab pertanyaan ini dalam \(n\) langkah. Setiap langkah merupakan operasi untuk menguji apakah sebuah bilangan dalam \(S\) tepat sama dengan \(x\text{.}\) Jadi, waktu eksekusi algoritma ini sebanding dengan \(n\text{,}\) dengan konstanta yang bergantung pada waktu yang diperlukan komputer untuk menjalankan operasi dasar berupa pemeriksaan apakah suatu bilangan bulat sama dengan nilai sasaran.

Soal kedua sedikit lebih menantang. Kini tampaknya kita harus mempertimbangkan himpunan-himpunan bagian beranggota \(3\) dari sebuah himpunan berukuran \(10,000\text{.}\) Ada \(C(10,000,3)\) himpunan bagian semacam itu. Memeriksa apakah jumlah tiga bilangan sama dengan \(143,297\) memang sangat mudah, tetapi ada sangat banyak himpunan yang harus diperiksa. Perhatikan bahwa \(C(10,000,3)=166,616,670,000\text{,}\) dan tidak banyak komputer yang mampu menangani operasi sebanyak ini. Lebih jauh lagi, jika daftar itu diperbesar menjadi satu juta bilangan, terdapat lebih dari \(10^{17}\) tripel yang harus diperiksa, dan jumlah itu berada di luar jangkauan perangkat keras masa kini.

Meskipun demikian, kita dapat membahas kasus umumnya. Kita diberi sebuah himpunan \(S\) yang terdiri atas \(n\) bilangan bulat dan sebuah bilangan \(x\text{.}\) Kemudian kita ditanya apakah ada tiga bilangan bulat dalam \(S\) yang jumlahnya \(x\text{.}\) Algoritma yang telah kita uraikan akan memiliki waktu eksekusi yang sebanding dengan \(n^3\text{.}\) Konstanta kesebandingannya bergantung pada waktu yang diperlukan untuk memeriksa apakah jumlah suatu tripel bilangan sama dengan \(x\text{.}\) Tentu saja, lamanya pengujian itu pada gilirannya bergantung pada seberapa besar nilai bilangan bulat \(x\) dan bilangan-bilangan bulat dalam \(S\text{.}\)

Soal ketiga berbeda. Pertama-tama, soal ini tampak jauh lebih sulit. Ada \(2^{n-1}\) pasangan himpunan bagian yang saling melengkapi dari suatu himpunan berukuran \(n\text{,}\) dan salah satu pasangan tersebut terdiri atas himpunan kosong dan seluruh himpunan. Dengan demikian, masih tersisa \(2^{n-1}-1\) pasangan yang harus diperiksa. Setiap pemeriksaan itu sendiri tidak terlalu sulit. Sebuah netbook dapat dengan mudah menentukan apakah dua himpunan bagian mempunyai jumlah yang sama, bahkan ketika kedua himpunan tersebut membentuk partisi dari sebuah himpunan berukuran \(10,000\text{.}\) Namun, ada sekitar \(10^{3000}\) partisi yang harus diperiksa, dan tidak ada perangkat keras di planet ini yang mampu menangani tugas tersebut. Jika ukurannya dinaikkan menjadi \(1,000,000\text{,}\) gabungan daya komputasi seluruh mesin di bumi pun tidak akan mampu menyelesaikannya.

Dalam situasi ini, kita memang memiliki sebuah algoritma, yaitu memeriksa semua partisi, tetapi algoritma tersebut sama sekali tidak praktis untuk himpunan beranggota \(n\) ketika \(n\) besar karena waktu eksekusinya sebanding dengan \(2^n\text{.}\)

Masing-masing dari ketiga soal yang telah kita ajukan berbentuk pertanyaan “ya/tidak”. Jawaban “ya” untuk soal mana pun dapat dibenarkan dengan memberikan sebuah sertifikat yang dapat diperiksa secara efisien. Sebagai contoh, jika Anda menjawab ya untuk pertanyaan pertama, Anda dapat memberikan informasi tambahan bahwa bilangan bulat \(83,172\) terdapat pada baris \(584\) dalam berkas masukan. Tentu saja, Anda juga dapat memberikan kode sumber program komputer tersebut dan meminta seorang pemeriksa menjalankan seluruh prosedurnya.

Demikian pula, jika Anda menjawab ya untuk pertanyaan kedua, Anda dapat menyebutkan ketiga bilangan tersebut beserta letaknya dalam berkas masukan. Jika diperlukan, seorang pemeriksa yang tidak memihak kemudian dapat memastikan bahwa jumlah ketiga bilangan bulat itu benar-benar \(143,297\) dan bahwa bilangan-bilangan tersebut memang berada di tempat yang disebutkan dalam berkas masukan. Sebagai alternatif, Anda dapat kembali memberikan kode sumber, yang mengharuskan pemeriksa menguji semua tripel dan memastikan bahwa ada satu tripel yang memenuhi syarat.

Serupa dengan itu, jawaban ya untuk pertanyaan ketiga memiliki sertifikat berukuran wajar. Anda hanya perlu menyebutkan unsur-unsur himpunan bagian \(A\text{.}\) Pemeriksa, yang dilengkapi komputer, dapat (a) memastikan bahwa semua bilangan dalam \(A\) termasuk dalam \(S\text{;}\) (b) menyusun daftar himpunan bagian \(B\) yang terdiri atas bilangan-bilangan bulat dalam \(S\) yang tidak termasuk dalam \(A\text{;}\) dan (c) menghitung jumlah bilangan bulat dalam \(A\) serta jumlah bilangan bulat dalam \(B\text{,}\) lalu memastikan bahwa kedua jumlah tersebut sama. Akan tetapi, dalam kasus ini Anda tidak akan memberikan kode sumber algoritma karena tampaknya tidak ada strategi yang masuk akal untuk memutuskan soal tersebut ketika ukuran soalnya besar (setidaknya, pembahasan kita sejauh ini belum memberikan strategi semacam itu).

Sekarang mari kita pertimbangkan keadaan ketika jawabannya “tidak”. Jika jawaban untuk pertanyaan pertama adalah tidak, sertifikatnya sekali lagi dapat berupa program komputer yang memungkinkan pemeriksa meninjau semua unsur \(S\) dan memastikan bahwa bilangan yang dimaksud tidak ada. Hal serupa berlaku untuk pertanyaan kedua, i.e., program itulah sertifikatnya.

Namun, keadaan untuk pertanyaan ketiga sekali lagi sangat berbeda. Kita tidak dapat mengatakan kepada pemeriksa, “Kami telah memeriksa semua kemungkinan dan tidak ada satu pun yang berhasil.” Pernyataan itu mustahil benar. Kita juga tidak memiliki program komputer yang dapat dijalankan oleh kita ataupun oleh pemeriksa. Hal terbaik yang dapat kita katakan ialah bahwa kita telah mencoba mencari partisi yang sesuai, tetapi tidak berhasil menemukannya. Akibatnya, kita tidak mengetahui jawaban yang sebenarnya untuk pertanyaan tersebut.

Banyak algoritma yang kita kembangkan dalam buku ini, serta banyak program komputer yang dihasilkan dari algoritma-algoritma tersebut, melibatkan langkah-langkah dasar yang disebut operasi. Arti kata operasi sengaja dibiarkan sebagai gagasan yang tidak didefinisikan secara presisi. Sebuah operasi mungkin sekadar membandingkan dua bilangan bulat untuk mengetahui apakah keduanya sama; mungkin memperbarui nilai sebuah variabel \(x\) dengan menggantinya menjadi \(x^2-3x+7\text{;}\) atau mungkin memeriksa apakah jumlah dua himpunan sama. Dalam contoh ketiga, biasanya kita akan membatasi ukuran kedua himpunan bagian serta besarnya bilangan-bilangan bulat di dalamnya. Karena itu, kita ingin dapat mengatakan bahwa terdapat suatu konstanta \(c\) sedemikian sehingga sebuah operasi dapat dijalankan pada komputer dalam waktu paling lama \(c\text{.}\) Komputer yang berbeda menghasilkan nilai \(c\) yang berbeda, tetapi perbedaan ini dapat kita abaikan dengan aman.

Soal dapat memiliki berbagai ukuran. Ketiga soal yang telah kita bahas dalam bab ini mempunyai ukuran masukan yang sama. Secara kasar, ukurannya adalah \(10,000\) blok, dengan setiap blok mampu memuat sebuah bilangan bulat yang besarnya paling tinggi \(100,000\text{.}\) Dalam buku ini, kita akan mengatakan bahwa ukuran masukan soal tersebut adalah \(n=10,000\text{,}\) dan dalam arti tertentu mengabaikan persoalan mengenai besarnya bilangan-bilangan bulat dalam himpunan itu. Pendekatan ini jelas memiliki keterbatasan. Kita dapat saja diberi sebuah himpunan \(S\) berukuran \(1\) dan sebuah calon unsur \(x\text{,}\) lalu ditanya apakah \(x\) termasuk dalam \(S\text{.}\) Sekarang, andaikan \(x\) merupakan untai bit sebesar cakram padat biasa, i.e., panjangnya sekitar \(700\) megabita. Membaca satu-satunya entri dalam \(S\) untuk mengetahui apakah entri tersebut tepat sama dengan \(x\) saja akan memerlukan waktu.

Dengan gagasan serupa, pertimbangkan soal menentukan apakah sebuah berkas \(x\) berada di suatu tempat dalam struktur direktori di bawah \(y\) pada sistem berkas Unix. Jika Anda hanya menggunakan nama sebagai dasar pencarian, soal ini mungkin relatif mudah. Namun, bagaimana jika Anda ingin memastikan bahwa terdapat salinan persis dari \(x\text{?}\) Soal itu kini menjadi jauh lebih menantang.