Mengukur keacakan rumus CNF

12

Sudah banyak diketahui bahwa formula CNF dapat secara kasar dipartisi dalam 2 kelas besar: acak vs. terstruktur. Rumus CNF terstruktur, bertentangan dengan rumus CNF acak, menunjukkan semacam keteraturan, menunjukkan pola yang tidak mungkin terjadi secara kebetulan. Namun, orang dapat menemukan formula terstruktur yang menunjukkan tingkat keacakan (yaitu kelompok klausa tertentu tertentu tampaknya jauh lebih terstruktur daripada yang lain), serta rumus acak dengan beberapa bentuk struktur yang lemah (yaitu kelompok klausa tertentu tertentu tampaknya kurang acak daripada yang lain ). Oleh karena itu tampaknya keacakan rumus bukan hanya fakta ya / tidak.

Misalkan menjadi fungsi yang, mengingat rumus CNF F F , mengembalikan nilai riil antara 0 dan 1 inklusif: 0 berarti rumus terstruktur murni, sedangkan 1 berarti rumus acak murni.r:F[0,1]FF0101

Saya bertanya-tanya apakah seseorang pernah mencoba untuk menciptakan . Tentu saja nilai yang dikembalikan oleh r akan (setidaknya ini maksud saya) hanya pengukuran praktis sesuai dengan beberapa kriteria yang masuk akal, daripada kebenaran teoritis yang solid.rr

Saya juga tertarik untuk mengetahui apakah seseorang pernah mendefinisikan dan mempelajari indikator statistik apa pun yang dapat digunakan dalam definisi , atau dalam menentukan properti keseluruhan berguna lainnya dari suatu formula. Dengan indikator statistik saya maksudkan sesuatu seperti itu:r

  1. HCV (Hit Hitung Variance)

    Mari menjadi fungsi yang, diberi variabel v jN , mengembalikan jumlah kali v j muncul di F . Biarkan V adalah himpunan variabel yang digunakan dalam F . Biarkan ˉ h F = 1hF:NNvjNvjFVFmenjadi AHC (rata Hit Count). HCV yang didefinisikan sebagai berikut: HVC=1h¯F=1|V|vjVhF(vj)

    Dalam kasus acak, HCV sangat rendah (semua variabel disebutkan hampir sama dengan jumlah kali), sedangkan dalam kasus terstruktur tidak (beberapa variabel) digunakan sangat sering dan beberapa yang lain tidak, yaitu ada "kelompok penggunaan").HVC=1|V|vjV(hF(vj)h¯F)2





  2. hF+(vj)vjhF(vj)i:N[0,1]vjVi(vj)i(vj)=2min(hF+(vj),hF(vj))hF(vj)

    AID=1|V|vjVi(vj)

    0.511



  3. 0.5

    IDV=1|V|vjV(i(vj)AID)2

    00

Motivasi

  1. Untuk lebih memahami bagaimana rumus CNF bekerja, bagaimana keacakan / strukturnya dapat diukur, jika sifat keseluruhan lainnya yang berguna dapat disimpulkan dengan melihat indikator statistik mereka, jika dan bagaimana indikator tersebut dapat digunakan untuk mempercepat pencarian.
  2. Bertanya-tanya apakah kepuasan (atau bahkan jumlah solusi) dari formula CNF dapat disimpulkan dengan hanya memanipulasi indikator statistiknya secara cerdik.

Pertanyaan

  1. Apakah ada yang pernah mengusulkan cara untuk mengukur keacakan rumus CNF?
  2. Adakah yang pernah mengusulkan indikator statistik apa pun yang dapat digunakan untuk mempelajari atau bahkan secara mekanis menyimpulkan sifat keseluruhan yang berguna dari formula CNF?
Giorgio Camerani
sumber
1
lihat makalah dalam jawaban ini ( cstheory.stackexchange.com/questions/4321/… ). Ini bisa memberi Anda tip tentang cara mendefinisikan r
Marcos Villagra
1
diskusi yang mungkin relevan untuk mengukur keacakan bit-string mathoverflow.net/questions/37518/…
Yaroslav Bulatov
Saya bisa mengatakan ini banyak kepada Anda karena saya telah mengerjakan ini sendiri untuk sementara waktu. Jika Anda mempertimbangkan SAT, rumus untuk 1 & 2 adalah eksponensial. Di sisi lain untuk k-SAT rumus untuk 1 & 2 adalah polinomial. Ini berhubungan dengan DEFINISI PRECISE saya tentang RANDOM K-SAT PERTANYAAN, yang sepertinya tidak ada yang mau menjawab.
Tayfun Bayar
@ Geekster: Apakah Anda ingin memberikan jawaban di sini?
Hsien-Chih Chang 張顯 之
@ Geekster: Apa maksudmu dengan "... rumus untuk 1 & 2 adalah eksponensial" ?
Giorgio Camerani

Jawaban:

3

Saya menyarankan untuk meminjam intuisi fisika bahwa struktur "kurang acak" lebih simetris. Simetri untuk CNF adalah setiap transformasi variabel, yang membuat fungsi tidak berubah. Dengan kriteria itu, fungsi 3 variabel seperti

x1x2x3.

atau, katakanlah,

(x1x2¬x3)(x1¬x2x3)(¬x1x2x3)(¬x1¬x2¬x3).

kurang acak daripada, katakanlah

(x1x2¬x3)(x1¬x2x3)(¬x1¬x2x3).

Secara umum, mendefinisikan konsep "acak" pada struktur hingga adalah menantang. Secara historis, itu dicoba pada urutan biner, yang bisa dibilang adalah struktur hingga paling sederhana. Misalnya, secara intuitif, urutan 01010101 "kurang acak" daripada, katakanlah, 01001110. Namun, dengan cepat disadari bahwa tidak ada definisi formal yang konsisten dari urutan acak terbatas ! Oleh karena itu, kita harus skeptis terhadap upaya naif untuk menentukan ukuran keacakan untuk setiap struktur yang terbatas.

Tegiri Nenashi
sumber
Saya sepenuhnya setuju dengan intuisi "struktur berarti keberadaan simetri, sedangkan keacakan berarti tidak adanya simetri" . Anda merujuk pada simetri sintaksis (sedangkan simetri semantik adalah yang mengubah fungsi tetapi membiarkan ruang solusi tidak berubah). Saya selalu yakin bahwa simetri adalah kuncinya.
Giorgio Camerani
1
@Walter: Gagasan simetri adalah upaya untuk meningkatkan aljabar daripada algoritma: kompleksitas algoritmik adalah ukuran yang menentang definisi konsisten untuk objek yang terbatas. Tapi kemudian kita harus menetapkan ukuran kompleksitas untuk setiap elemen dalam suatu kelompok (misalnya, transformasi yang meniadakan variabel tunggal lebih sederhana daripada yang meniadakan dua) - ini terasa seperti hanya mendorong masalah di sekitar ...
Tegiri Nenashi