Setelah rilis perpustakaan AIGER untuk menangani dan-inverter grafik sekitar tahun 2006 (saya pikir), beberapa pemecah sirkuit SAT dirilis pada 2006-2008, dan dalam beberapa lomba / Kompetisi SAT ada trek AIG. Namun sejak itu tampaknya fokus telah sepenuhnya pada SMT atau meningkatkan pemecah klausa SAT.
Secara intuitif saya berkonsentrasi pada sirkuit SAT tampaknya masuk akal: Banyak jika tidak sebagian besar masalah lebih alami dinyatakan sebagai sirkuit SAT daripada CNF; sirkuit memberikan informasi struktural yang tidak dapat direkayasa balik dari CNF, tetapi sirkuit selalu dapat diubah menjadi CNF; dan setidaknya bidang industri yang signifikan dari sintesis logika tampaknya sangat cocok untuk AIG.
Jadi apa yang terjadi? Apakah ternyata informasi struktural tambahan tidak membantu pemecah masalah? Apakah SAT berbasis AIG menyelesaikan percobaan yang gagal?
sumber
Jawaban:
ada banyak sudut berbeda pada pertanyaan Anda. umumnya setuju dengan premis Anda bahwa melihat "informasi struktural" dalam formulasi SAT harus menjadi area penelitian yang sangat baik.
SAT yang dikodekan dalam CNF telah menjadi standar selama beberapa dekade. itu dipadatkan pada awal hingga pertengahan 1990-an dengan format / kompetisi DIMACS .
apa yang secara teknis "informasi struktural"? mungkin sulit untuk secara formal menolak konsep itu dan menghindari lingkaran yang hampir tautologis. sebenarnya tidak ada perbedaan antara penyandian SAT CNF dan dan penyandian lain yang mempertahankan struktur jaringan. ini diwujudkan dalam konsep "klausa / variabel grafik" yang cenderung digunakan oleh banyak pemecah SAT. dengan kata lain, dalam arti kasar, setiap pemecah SAT yang signifikan menggunakan "informasi struktural" .
ya, arahan baru dalam penelitian telah berfokus pada pemecahan ASP dan SMT yang hampir benar-benar mewujudkan "informasi struktural" yang Anda tanyakan.
Transformasi Tseytin dengan mudah mengubah suatu sirkuit menjadi SAT dalam waktu / ruang P untuk input ke pemecah SAT standar. itu mungkin banyak digunakan dalam banyak konteks terutama konteks sirkuit EE.
ada beberapa penelitian yang agak terisolasi secara umum di sepanjang garis yang Anda sebutkan tetapi sayangnya (sekali lagi dengan premis Anda) sepertinya tidak pernah berkembang banyak menjadi tren penelitian. jangan berpikir itu karena kurangnya potensi tetapi lebih banyak faktor manusia. dua makalah favorit [1] [2], yang lain adalah untuk melihat contoh-contoh khusus dari bidang-bidang seperti "contoh industri" atau contoh "teknik listrik" di mana ada beberapa penelitian khusus.
Puritan CS kadang-kadang cenderung ingin menghindari pertimbangan psikologi / sosiologi dalam semua abstraksi matematika, tetapi cukup masih merupakan faktor dalam ilmu komputer . Anda bertanya tentang tren penelitian, yang didasarkan pada faktor psikologis manusia. mungkin ada beberapa efek lampu jalan yang terjadi di sini alias "buah tergantung rendah". orang mungkin mengatakan / mempertimbangkan bahwa bahkan sekarang beberapa dekade, penelitian algoritme SAT masih dalam tahap awal, sehingga pertanyaan-pertanyaan besar seperti P vs NP tidak terlihat, dan mungkin penelitian yang sudah ada sementara masih substansial masih hanya "menggaruk permukaan" .
[1] Mengurai masalah kepuasan atau Menggunakan grafik untuk mendapatkan wawasan yang lebih baik tentang masalah kepuasan , Herwig 2006 (83pp)
[2] Tepian pisau kendala Walsh 1998
sumber