Batas Atas Terbaik di SAT

43

Di utas lain , Joe Fitzsimons bertanya tentang "batas bawah terbaik saat ini pada 3SAT."

Saya ingin pergi ke arah lain: Apa batas atas terbaik saat ini di 3SAT? Dengan kata lain, apa kompleksitas waktu dari pemecah SAT yang paling efisien?

Secara khusus, apakah mungkin untuk menemukan algoritma sub-eksponensial (namun super polinomial) untuk SAT?

cc.complexity-theory ds.algorithms sat upper-bounds MS Dousti
sumber

2

Saya tidak tahu tentang hasil analitik, tetapi Anda dapat menemukan hasil eksperimen di sini baldur.iti.uka.de/sat-race-2010/result.html (lihat tautan "HTML")

Radu GRIGore

1

judul pertanyaan ini agak menyesatkan, karena adanya pertanyaan ini: cstheory.stackexchange.com/questions/1295/sat-solver-download . Saya pikir Anda mungkin menguraikan kembali sebagai 'Batas Atas Terbaik di SAT'?

Suresh Venkat

@ Suresh: Pertanyaan yang Anda maksud berkaitan dengan "#SAT", sementara yang ini berhubungan dengan SAT. Selain itu, pertanyaan itu diajukan sekitar satu minggu setelah ini. Bagaimanapun, apakah Anda masih menyarankan untuk mengubah judul yang ini?

MS Dousti

ya, karena "SAT Solver" adalah objek terkenal yang spesifik - basis kode aktual untuk memecahkan SAT. Google akan menjadi bingung dan mengarahkan orang yang mencari kode di sini :).

Suresh Venkat

4

Mengenai motivasi untuk pertanyaan ini, saya pikir beberapa orang telah mencoba pemecah SAT pada contoh 17x17. Tampaknya menjadi batas dari apa yang bisa ditangani dengan pemecah SAT. Anda bisa mencoba solver paralel, tetapi saya mendapat kesan berdasarkan posting Bill Gasarch bahwa Anda akan membutuhkan upaya skala besar. Anda juga bisa menerapkan pemecah SMT dengan teori yang sesuai, atau menggunakan pemecah kendala yang mengimplementasikan kendala global yang memiliki penyebar yang efisien. Dalam masing-masing kasus, ide baru adalah untuk mengekspresikan properti penting yang sulit dilakukan dengan menggunakan klausa.

András Salamon

38

Ada dua jenis pemecah SAT "terbaik", satu untuk teori, satu untuk praktik.

Teori

Kazuo Iwama, Kazuhisa Seto, Tadashi Takai, Suguru Tamaki, " Peningkatan Algoritma Acak untuk 3-SAT ", ISAAC 2010.

acak untuk 3SAT. $O(1.32113^n)$

Timon Hertli, Robin A. Moser, Dominik Scheder, " Meningkatkan PPSZ untuk 3-SAT menggunakan Variabel Kritis ", 2011.

acak untuk 3SAT. $O(1.321^n)$

Konstantin Kutzkov, Dominik Scheder, " Menggunakan CSP Untuk Meningkatkan Deterministik 3-SAT ", 2010.

deterministik untuk 3SAT. $O(1.439^n)$

Praktek

Periksa konferensi SAT untuk hasil kompetisi untuk setiap tahun.

Tian Liu
sumber

Saya menemukan tautan ke Iwama et al. kertas . Jadi, apakah

benar-benar hasil terbaru dan terbaik untuk memecahkan SAT sampai sekarang?

O ({1.32113}^{n})

$O(1.32113^n)$

MS Dousti

@ Sadeq: Saya kira begitu, tetapi hanya untuk 3-SAT, bukan SAT.

Tian Liu

2

Sekarang algoritma terbaik adalah dalam waktu

oleh Timon Hertli, Robin A. Moser dan Dominik Scheder.

O ({1.321}^{n})

$O(1.321^n)$

Tian Liu

10

Namun lain update: di Focs 2011, Timon Hertli ( arxiv.org/abs/1103.2165 ) membuktikan bahwa memecahkan algoritma PPSZ setiap 3SAT misalnya dalam

waktu.

{1.308}^{n}

$1.308^n$

Ryan Williams

21

Saya tidak mengetahui adanya algoritma acak nol-kesalahan (atau algoritma coNE / Eadvice ,
dalam hal ini) untuk SAT yang memiliki batas yang lebih baik daripada algoritma deterministik yang diketahui,
terlepas dari apakah ada atau tidak dijanjikan akan paling banyak satu tugas yang memuaskan.

Derandomisasi Algoritma HSSW untuk 3-SAT menunjukkan hal itu

$\overset{\sim}{O}(1.3303^n)$

Derandomisasi PPSZ untuk Unique-k-SAT menunjukkan bahwa:

$n$
$O\hspace{.02 in}(1.3071^n)$ $O\hspace{.02 in}(1.4699^n)$

3-SAT Lebih Cepat dan Lebih Sederhana - Batas-SAT Unik untuk PPSZ Hold secara Umum menunjukkan bahwa (awalnya disebutkan dalam komentar Ryan )

$O\hspace{.02 in}(1.30704^n)$

$O\hspace{.02 in}(1.46899^n)$

Menembus PPSZ Barrier for Unique 3-SAT
mengklaim hasil yang dapat diringkas sebagai berikut:

"Ada algoritma acak untuk unik-3-SAT sehingga untuk $\: \epsilon = 1\hspace{-0.03 in}\big/\hspace{-0.06 in}\left(\hspace{-0.03 in}10^{\hspace{.02 in}24}\hspace{-0.04 in}\right) \:$
$S$
$\: O\hspace{-0.04 in}\left(2^{(S+o(1))\cdot n}\right) \:$ , $\;$ algoritma kertas saat ini berjalan dalam waktu $\: O\hspace{-0.04 in}\left(2^{(S-\epsilon+o(1))\cdot n}\right)$

Komunitas
sumber

16

$O(a^n)$ $a = 2(k-1)/k$ $O(1.33334^n)$ $O(1.5^n)$

$O((a+\epsilon)^n)$ $a$ $\epsilon>0$

$O^*$

Robin Kothari
sumber

1

Mengapa Anda mengatakan "hampir sepenuhnya"? Apakah saya melewatkan sesuatu di koran?

András Salamon

1

O ((2 - \frac{2}{k + 1})^{n})

$O((2 - \frac{2}{k + 1})^n)$

k = 3

$k = 3$

O ({1.5}^{n})

$O(1.5^n)$

4

Saya mengatakan "hampir sepenuhnya" hanya untuk menunjukkan bahwa ada faktor epsilon di sana. Saya kira orang akan berharap bahwa derandomisasi lengkap mencapai waktu berjalan yang sama (hingga faktor polinomial). Atau mungkin itu tidak masuk akal untuk diharapkan.

Robin Kothari

1

@Grigory Yaroslavtsev: Bukankah algoritma deterministik Moser-Scheder untuk kSAT yang saya sebutkan lebih cepat daripada yang Anda kutip? Apakah saya melewatkan sesuatu?

Robin Kothari

1

ϵ

$\epsilon$

12

Seperti yang telah disebutkan, jika Anda tertarik pada jaminan waktu berjalan teoritis, pertanyaan ini adalah duplikat.

Tetapi saya ingin menunjukkan bahwa jika Anda benar-benar ingin menyelesaikan masalah nyata (seperti masalah pewarnaan yang Anda sebutkan), saya pikir sama sekali tidak masuk akal untuk mempelajari batas atas teoretis.

Meskipun Anda ingin menghindari aspek "rekayasa", saya sarankan Anda hanya mengambil beberapa pemecah SAT yang populer, mencobanya, dan lihat apa yang terjadi (kebanyakan dari mereka dapat membaca format file DIMACS yang sama, sehingga mudah untuk mencoba pemecah yang berbeda). Anda mungkin memiliki kejutan positif dan negatif. Baru-baru ini saya memiliki keluarga instance SAT; banyak contoh dengan puluhan ribu variabel dan lebih dari satu juta klausa ternyata mudah untuk diselesaikan, sementara contoh yang tampaknya lebih sederhana dengan hanya ratusan variabel dan ribuan klausa yang terlalu sulit untuk setiap pemecah yang saya coba.

Jukka Suomela
sumber

8

Selain ringkasan Jukka, perlu juga dicatat bahwa ada dua jenis utama pemecah SAT: yang didasarkan pada propagasi survei, yang bekerja dengan baik untuk instance SAT acak, dan mereka yang menggunakan pembelajaran klausa dikombinasikan dengan resolusi unit, yang cenderung bekerja baik untuk menemukan struktur kombinatorial. Ini memiliki perilaku yang sangat berbeda. Kasus terburuk untuk pemecah SAT cenderung menjadi contoh yang tidak memuaskan, tetapi di mana ruang nogood memiliki struktur kompleks yang tidak memungkinkan banyak pemangkasan. Sayangnya contoh dari kombinatorik cenderung seperti ini.

András Salamon

11

Timon Hertli, " 3-SAT Lebih Cepat dan Lebih Sederhana - Batas SAT-Unik untuk PPSZ Ditahan Secara Umum ", FOCS 2011.

$O(1.308^n)$

Kaveh
sumber

Saya berasumsi bahwa ketika seseorang datang dengan batas atas yang lebih baik mereka akan mengutip makalah ini. Hanya ada satu kali kutipan untuk makalah ini, yaitu "Algoritma Kepuasan dan Kekerasan Kasus Rata-Rata untuk Rumus di Atas Binary Penuh Basis" Dan mereka tampaknya berbicara tentang hanya jenis formula tertentu. Oleh karena itu, ini tampaknya menjadi Upper Bound terbaik sejauh ini.

Tayfun Bayar

@TayfunPay:

$\:$ Kertas bawah dalam jawaban saya mengutip kertas itu.

$\;\;\;\;$

@RickyDemer Uhuh! apakah ini lebih baik daripada ini? Notasi tidak begitu jelas bagi saya.

Tayfun Bayar

@TayfunPay:

$\:$ Ya, dan Anda dapat menelusuri kedua kertas seperti yang dijelaskan di bawah ini.

$\:$

S_{3}

$S_3$

S_{k}

$S_k$

$\:$ Di bagian atas halaman 11, makalah itu mengatakan algoritma mereka memberikan batasan yang sama dengan PPSZ, yang berarti mereka tidak menunjukkan apa pun lebih dari yang saya sebutkan dalam kalimat saya sebelumnya.

$\:$ (lanjutan ...)

$\hspace{.35 in}$

(... lanjutan)

$\:$

S

$S$

2^{S \cdot n}

$2^{S\cdot n}$

$\:$

S

$S$

S_{3}

$S_3$

$\;\;\;$

8

Mustahil bagi 3SAT untuk memiliki algoritma sub-eksponensial kecuali jika hipotesis waktu eksponensial salah.

Kazuo Iwama, Suguru Tamaki, Peningkatan batas atas untuk 3-SAT , 2004.

$O({1.324}^n)$

Daniel Rolf, Improved Bound untuk Algoritma PPSZ / Schoning untuk 3-SAT , 2005.

$O({1.32216}^n)$

Mohammad Al-Turkistany
sumber

15

Bukankah itu sebuah tautologi?

Tsuyoshi Ito

1

2^{o (n)}

$2^{o(n)}$

Karya Kazuo Iwama et al. (2004) lebih baru dari Schoening (1999). Saya ingin tahu apakah hasil yang lebih baru tersedia.

MS Dousti

8

Untuk menghindari kemungkinan kebingungan, komentar terakhir saya merujuk pada kalimat pertama dari jawaban: "Tidak mungkin bagi 3SAT untuk memiliki algoritma sub-eksponensial kecuali hipotesis waktu eksponensial (ETH) salah." Pemahaman saya adalah waktu eksponensial-waktu hipotesis adalah hipotesis yang sangat menyatakan bahwa tidak ada algoritma untuk 3SAT yang waktu berjalannya subeksponensial (yaitu 2 ^ {o (n)}) dalam jumlah variabel.

Tsuyoshi Ito

10

Dan untuk menghindari kebingungan lebih lanjut, saya akan menambahkan bahwa ketika Tsuyoshi memposting komentarnya, jawabannya hanya berisi satu kalimat, yang membuat komentarnya sangat tepat.

Robin Kothari

7

Posting ini berkaitan dengan batas atas pada SAT. Ini salah satu penawaran dengan batas bawah terbaik. Tautan ini memberikan detail kompetisi tahunan yang membandingkan implementasi SAT solver, yang semuanya dapat diunduh. Untuk kesederhanaan, Anda bisa mulai dengan SAT4J , perpustakaan berbasis Java untuk pemecahan SAT.

Dave Clarke
sumber

Ternyata pertanyaan ini sudah ditanyakan sebelumnya; Saya hanya tidak melihatnya ketika saya mencari di situs web. Tanggapan Tian Liu pada pertanyaan batas atas adalah persis apa yang saya cari. Terima kasih atas tautannya, dave!

Daniel Apon

1

Ini bukti bahwa saya menghabiskan terlalu banyak waktu di sini ;-)

Dave Clarke

kami senang Anda melakukannya :)

Suresh Venkat

2

Saya tidak yakin apakah saya akan merekomendasikan sat4J, tidak hanya secara signifikan lebih lambat daripada yang canggih tapi juga agak lebih kompleks. Memang benar, bagaimanapun, bahwa itu dapat disesuaikan dengan baik karena struktur berorientasi objek. MiniSat ditulis dengan sangat baik dan 2.2 adalah yang mutakhir.

Mikolas

3

Algoritma deterministik terbaik untuk 3-SAT sekarang memiliki batas atas 1,32793 ^ n, lihat https://arxiv.org/abs/1804.07901 oleh Sixue Liu. Pada dasarnya batas atas untuk semua k-SAT telah diperbaiki dalam makalah ini.

PADA KI Wong
sumber

Batas Atas Terbaik di SAT

Jawaban:

Teori

Praktek