Contoh di mana keunikan solusi membuatnya lebih mudah ditemukan

Kelas kompleksitas terdiri dari masalah-masalah yang dapat diputuskan oleh mesin Turing waktu polinomial nondeterministic yang memiliki paling banyak satu yang menerima jalur komputasi. Artinya, solusinya, jika ada, unik dalam pengertian ini. Diperkirakan sangat tidak mungkin bahwa semua masalah ada di , karena oleh Teorema Valiant-Vazirani ini akan menyiratkan keruntuhan .$\mathsf{UP}$$\mathsf{NP}$$\mathsf{UP}$$\mathsf{P}$$\mathsf{NP}=\mathsf{RP}$

Di sisi lain, tidak ada dikenal sebagai -complete, yang menunjukkan bahwa persyaratan solusi unik masih membuat mereka lebih mudah.$\mathsf{UP}$$\mathsf{NP}$

Saya mencari contoh, di mana asumsi keunikan mengarah ke algoritma yang lebih cepat.

Sebagai contoh, dengan melihat masalah grafik, dapatkah klik maksimum dalam grafik ditemukan lebih cepat (walaupun mungkin masih dalam waktu eksponensial), jika kita tahu bahwa grafik tersebut memiliki klik maksimum yang unik ? Bagaimana dengan colorability yang unik, jalur Hamilton yang unik, set dominasi minimum yang unik, dll.?$k$

Secara umum, kita dapat mendefinisikan versi solusi-unik dari setiap masalah -complete, menskalakannya ke . Apakah diketahui ada di antara mereka yang menambahkan asumsi keunikan mengarah ke algoritma yang lebih cepat? (Mengizinkan itu masih tetap eksponensial.)$\mathsf{NP}$$\mathsf{UP}$

3-SAT mungkin salah satu masalah seperti itu. Saat ini batas atas terbaik untuk Unique 3-SAT secara eksponensial lebih cepat daripada untuk 3-SAT umum. (Speedup bersifat eksponensial, meskipun pengurangan eksponen kecil.) Pemegang rekor untuk case unik adalah makalah ini oleh Timon Hertli.

Algoritma Hertli ini dibangun berdasarkan penting algoritma PPSZ dari Paturi, Pudlák, Saks, dan Zane untuk -SAT, yang saya percaya masih yang tercepat untuk k ≥ 5 (lihat juga ini artikel ensiklopedia). Analisis asli menunjukkan batas yang lebih baik untuk Unique k -SAT daripada untuk k -SAT umum ketika k = 3 , 4 ; kemudian, bagaimanapun, Hertli menunjukkan dalam makalah yang berbeda$k$$k \geq 5$$k$$k$$k = 3, 4$Anda bisa mendapatkan batas yang sama untuk algoritma PPSZ (sedikit tweak), tanpa mengasumsikan keunikan. Jadi, mungkin keunikan membantu, dan itu pasti dapat menyederhanakan analisis beberapa algoritma, tetapi pemahaman kita tentang peran keunikan untuk -SAT masih terus berkembang.$k$

Ada bukti bahwa Unique -SAT tidak terlalu mudah daripada k -SAT umum . Hipotesa Waktu Eksponensial Kuat (SETH) menyatakan tidak ada δ < 1 sehingga n -variabel k -SAT dapat dipecahkan dalam waktu O ∗ ( 2 δ n ) untuk setiap konstanta k ≥ 3 . Ditunjukkan dalam sebuah makalah Calabro, Impagliazzo, Kabanets, dan Paturi bahwa, jika SETH berlaku, maka pernyataan yang sama berlaku untuk Unique k -SAT. Juga, jika umum $k$$k$$\delta < 1$$n$$k$$O^*(2^{\delta n})$$k \geq 3$$k$$k$-SAT memerlukan waktu eksponensial, yaitu ada beberapa sehingga k -SAT umum tidak dapat diselesaikan dalam waktu O ∗ ( 2 ϵ n ) , maka hal yang sama harus berlaku untuk Unique 3-SAT. Lihat kertas untuk pernyataan paling umum. $k \geq 3, \epsilon > 0$$k$$O^*(2^{\epsilon n})$

(Catatan: notasi menekan faktor polinomial dalam panjang masukan.)$O^*$

2-Vertex jalur terputus masalah terpendek dalam grafik tidak berarah yang baru-baru ini diselesaikan (ICALP14) oleh A. Bjorklund dan T. Husfeldt. Tetapi solusi deterministik adalah untuk kasus keberadaan solusi unik. Dalam hal ada lebih dari satu solusi, mereka menunjukkan bahwa masalahnya adalah RP . Sebagai penulis makalah yang disebutkan, tidak diketahui apakah masalahnya ada di P dalam skenario umum.

Di luar teori kompleksitas dan analisis algoritma, asumsi bahwa hanya ada satu solusi yang menjadi dasar bagi beberapa aturan standar yang digunakan untuk menyimpulkan solusi dalam teka-teki Sudoku. Aturan-aturan ini umumnya melibatkan mencari cara di mana bagian-bagian dari puzzle mungkin dapat memiliki dua solusi atau lebih yang tidak berinteraksi dengan sisa puzzle. Itu tidak dapat terjadi dalam solusi aktual, jadi jika sebuah pola yang mengancam untuk menyebabkan ini ditemukan, maka itu harus rusak, memungkinkan pemecah masalah untuk menyimpulkan seperti apa solusi yang sebenarnya dapat terlihat. Lihat http://www.brainbashers.com/sudokuuniquerectangles.asp untuk beberapa contoh aturan deduksi berdasarkan keunikan.

Menyebutkan hasil lain oleh Björklund, jika Anda dijamin memiliki paling banyak satu siklus Hamiltonian dalam grafik, Anda dapat memutuskan apakah grafik adalah Hamiltonian lebih cepat daripada yang Anda bisa pada umumnya.$G$

Asumsi keunikan berarti paritas jumlah Ham. lintasan sama dengan memutuskan apakah grafiknya Hamiltonian.

$O(1.619^n)$$O^*(1.657^n)$$O(n^22^n)$