Subbab 4.4 Eksak versus Aproksimasi
Banyak masalah kombinatorial memiliki solusi “eksak”, dan dalam kasus seperti itu biasanya kita akan berusaha keras untuk menemukannya. Teorema Erdős–Szekeres yang telah dibahas sebelumnya dalam bab ini merupakan contoh yang baik dari hasil “eksak”. Maksud pernyataan ini adalah bahwa untuk setiap pasangan bilangan bulat positif \(m\) dan \(n\text{,}\) terdapat barisan yang terdiri atas \(mn\) bilangan real berbeda yang tidak memiliki subbarisan menaik dengan \(m+1\) suku maupun subbarisan menurun dengan \(n+1\) suku. Untuk melihatnya, perhatikan barisan \(\sigma\) yang didefinisikan sebagai berikut. Untuk setiap \(i=1,2,\dots,m\text{,}\) misalkan \(B_i=\{j+(i-1)n:1\le j\le n\}\text{.}\) Perhatikan bahwa setiap \(B_i\) merupakan blok yang terdiri atas \(n\) bilangan bulat berurutan. Selanjutnya, definisikan suatu permutasi \(\sigma\) dari \(mn\) bilangan bulat positif pertama dengan menetapkan \(\alpha\lt \beta\) apabila terdapat bilangan bulat \(i_1\) dan \(i_2\text{,}\) dengan indeks pertama lebih kecil daripada indeks kedua, sedemikian sehingga \(\alpha\in B_{i_1}\) dan \(\beta\in B_{i_2}\text{.}\) Selain itu, untuk setiap \(i=1,2,\dots,m\text{,}\) tetapkan \(\alpha\lt \beta\) dalam \(\sigma\) apabila \(1+(i-1)n\le \beta\lt \alpha\le in\text{.}\) Jelas bahwa setiap subbarisan menaik dari \(\sigma\) memuat paling banyak satu anggota dari setiap blok, sehingga \(\sigma\) tidak memiliki subbarisan menaik dengan \(m+1\) suku. Di sisi lain, setiap subbarisan menurun dalam \(\sigma\) termuat dalam satu blok, sehingga \(\sigma\) tidak memiliki subbarisan menurun dengan \(n+1\) suku.
1
Hasil eksak juga disebut “terbaik yang mungkin”, “tajam”, atau “ketat.”
Sebagai contoh lain dari solusi eksak, banyaknya solusi bilangan bulat untuk \(x_1+x_2+\dots x_r=n\) dengan \(x_i>0\) untuk \(i=1,2,\dots,r\) adalah tepat \(C(n-1,r-1)\text{.}\) Di sisi lain, belum ada satu pun hal yang telah kita bahas sejauh ini yang memungkinkan kita memberikan solusi eksak untuk banyaknya partisi dari suatu bilangan bulat \(n\text{.}\)
Subbagian 4.4.1 Solusi Aproksimasi dan Asimtotik
Berikut adalah contoh masalah terkenal yang hanya dapat kita bahas melalui solusi aproksimasi, setidaknya ketika ukuran masukannya cukup besar. Untuk suatu bilangan bulat \(n\text{,}\) misalkan \(\pi(n)\) menyatakan banyaknya bilangan prima di antara \(n\) bilangan bulat positif pertama. Sebagai contoh, \(\pi(12)=5\) karena \(2\text{,}\) \(3\text{,}\) \(5\text{,}\) \(7\text{,}\) dan \(11\) merupakan bilangan prima. Nilai eksak \(\pi(n)\) diketahui untuk \(n\le 10^{23}\text{,}\) dan bahkan:
\begin{equation*}
\pi(10^{23}) = 1,925,320,391,606,803,968,923
\end{equation*}
Di sisi lain, Anda mungkin bertanya apakah \(\pi(n)\) menuju tak hingga ketika \(n\) semakin besar. Jawabannya ya, dan berikut adalah argumen klasik yang cukup sederhana. Andaikan, sebaliknya, hanya terdapat \(k\) bilangan prima, dengan \(k\) suatu bilangan bulat positif. Andaikan \(k\) bilangan prima ini dicantumkan dalam urutan menaik sebagai \(p_1\lt p_2\lt \dots\lt p_k\text{,}\) lalu perhatikan bilangan \(n=1+p_1p_2\cdots p_k\text{.}\) Bilangan \(n\) tidak habis dibagi oleh satu pun dari bilangan prima tersebut dan nilainya lebih besar daripada \(p_k\text{.}\) Oleh karena itu, \(n\) merupakan bilangan prima yang lebih besar daripada \(p_k\) atau habis dibagi oleh suatu bilangan prima yang lebih besar daripada \(p_k\text{.}\)
Dengan demikian, kita mengetahui bahwa \(\lim_{n\rightarrow\infty}\pi(n)=\infty\text{.}\) Dalam keadaan seperti ini, matematikawan biasanya ingin mengetahui lebih jauh seberapa cepat \(\pi(n)\) menuju tak hingga. Sejumlah fungsi menuju tak hingga secara “lambat”, seperti \(\log n\) atau \(\log\log n\text{.}\) Fungsi lain menuju tak hingga dengan cepat, seperti \(2^n\text{,}\) \(n!\text{,}\) atau \(2^{2^n}\text{.}\) Karena \(\pi(n)\le n\text{,}\) fungsi tersebut tidak mungkin menuju tak hingga secepat ketiga fungsi terakhir, tetapi mungkin saja laju pertumbuhannya seperti \(\log n\) atau mungkin \(\sqrt{n}\text{.}\)
Berdasarkan hasil perhitungan (yang dilakukan dengan tangan, jauh sebelum komputer tersedia), pada tahun 1796 Legendre mengajukan konjektur bahwa \(\pi(n)\) menuju tak hingga seperti \(n/\ln n\text{.}\) Lebih tepatnya, ia mengajukan konjektur bahwa
\begin{equation*}
\lim_{n\rightarrow\infty}\frac{\pi(n)\ln n}{n}=1.
\end{equation*}
Pada tahun 1896, tepat seratus tahun setelah konjektur Legendre, Hadamard dan de la Vallée-Poussin secara terpisah menerbitkan pembuktian konjektur tersebut dengan menggunakan teknik yang berakar pada karya perintis Riemann dalam analisis kompleks. Hasil ini, yang kini cukup dikenal sebagai Teorema Bilangan Prima, hingga sekarang tetap menjadi topik yang banyak dipelajari pada perbatasan antara analisis dan teori bilangan.
Subbagian 4.4.2 Algoritma Waktu Polinomial
Di sepanjang buku ini, kita akan memberikan perhatian besar pada masalah yang dapat diselesaikan dalam waktu polinomial. Artinya, terdapat suatu konstanta \(c>0\) dan suatu algoritma \(\cgA\) untuk menyelesaikan masalah tersebut dengan waktu berjalan \(O(n^c)\text{,}\) dengan \(n\) sebagai ukuran masukan. Simbol \(\cgP\) mengingatkan kita pada kata polinomial.
Subbagian 4.4.3 \(\cgP=\cgN\cgP\text{?}\)
Mungkin pertanyaan paling terkenal pada perbatasan antara matematika kombinatorial, ilmu komputer teoretis, dan logika matematika adalah pertanyaan yang sangat sulit mengenai apakah \(\cgP\) sama dengan \(\cgN\cgP\text{.}\) Masalah ini biasa ditulis secara ringkas sebagai: \(\cgP=\cgN\cgP\text{?}\) Di sini, kami menyajikan pembahasan informal singkat mengenai masalah tersebut.
Pertama, kita telah memperkenalkan kelas \(\cgP\) yang terdiri atas semua masalah kombinatorial ya-tidak yang dapat diselesaikan dengan algoritma waktu polinomial. Dua masalah pertama yang dibahas dalam bab ini termasuk dalam \(\cgP\) karena masing-masing dapat diselesaikan dengan algoritma yang memiliki waktu berjalan \(O(n)\) dan \(O(n^3)\text{.}\) Menentukan apakah suatu graf dapat diwarnai dengan \(2\) warna dan apakah graf tersebut terhubung juga dapat dilakukan dengan algoritma waktu polinomial.
Perlu kami tekankan bahwa menentukan apakah suatu masalah termasuk dalam kelas \(\cgP\) atau tidak dapat menjadi sangat sulit. Sebagai contoh, kami belum mengetahui cara memberikan algoritma cepat untuk menyelesaikan masalah ketiga (jumlah subhimpunan), tetapi hal itu tidak berarti algoritma semacam itu tidak ada. Mungkin kita semua perlu belajar lebih keras!
Dengan mengesampingkan persoalan itu sejenak, kelas \(\cgN\cgP\) terdiri atas masalah ya–tidak yang, untuk jawaban ya, memiliki sertifikat yang kebenarannya dapat diverifikasi dalam waktu polinomial. Secara lebih formal, kelas ini disebut kelas masalah waktu polinomial nondeterministik. Masalah ketiga kita jelas termasuk dalam kelas ini.
Pertanyaan terkenalnya adalah apakah kedua kelas tersebut sama. Jelas bahwa setiap masalah yang termasuk dalam \(\cgP\) juga termasuk dalam \(\cgN\cgP\text{,}\) yakni \(\cgP\subseteq\cgN\cgP\text{,}\) tetapi apakah keduanya sama? Sulit membayangkan bahwa terdapat algoritma waktu polinomial untuk menyelesaikan masalah ketiga (masalah jumlah subhimpunan), dan belum ada seorang pun yang hampir menuntaskan persoalan ini. Namun, jika Anda memperoleh gagasan yang baik, pastikan untuk membahasnya dengan salah satu atau kedua penulis buku ini sebelum mengumumkan temuan Anda. Jika ternyata Anda benar, Anda tentu akan menghargai kesempatan berfoto bersama kami.
