Kompleksitas versi pencarian 2-SAT dengan asumsi

Jika $\mathsf{L = NL}$ , maka ada algoritma logspace yang memecahkan versi keputusan 2-SAT.

• Apakah $\mathsf{L = NL}$ diketahui menyiratkan bahwa ada algoritma ruang log untuk mendapatkan tugas yang memuaskan , ketika diberi instance 2-SAT yang memuaskan sebagai input?

• Jika tidak, bagaimana dengan algoritma yang menggunakan ruang sub-linear (dalam jumlah klausa)?

Mengingat satisfiable 2-CNF , Anda dapat menghitung tertentu memuaskan tugas e oleh NL-fungsi (yaitu, ada NL-predikat P ( φ , i ) yang memberitahu Anda apakah e ( x i ) benar). Salah satu cara untuk melakukannya dijelaskan di bawah ini. Aku bebas akan menggunakan fakta bahwa NL tertutup di bawah A C 0 -reductions, maka NL-fungsi ditutup di bawah komposisi; ini adalah konsekuensi dari NL = coNL.$\phi$$e$$P(\phi,i)$$e(x_i)$$\mathrm{AC}^0$

Biarkan menjadi 2-CNF yang memuaskan. Untuk setiap literal sebuah , biarkan sebuah → menjadi jumlah literal dicapai dari suatu oleh jalan diarahkan pada grafik implikasi φ , dan sebuah ← jumlah literal dari mana sebuah dicapai. Keduanya dapat dihitung dalam NL.$\phi(x_1,\dots,x_n)$$a$$a^\to$$a$$\phi$$\let\ot\leftarrow a^\ot$$a$

Perhatikan bahwa , dan ¯ sebuah ← = a → , karena condong-simetri dari grafik implikasi. Tentukan tugas e sehingga$\let\ob\overline \ob a^\to=a^\ot$$\ob a^\ot=a^\to$$e$

• jika , maka e ( a ) = 1 ;$a^\ot>a^\to$$e(a)=1$

• jika , maka e ( a ) = 0 ;$a^\ot<a^\to$$e(a)=0$

• jika , biarkan aku menjadi minimal sehingga x i atau ¯ x i muncul dalam komponen sangat terhubung dari sebuah (tidak bisa keduanya, sebagaimana φ adalah satisfiable). Masukkan e ( a ) = 1 jika x i muncul, dan e ( a ) = 0 sebaliknya.$a^\ot=a^\to$$i$$x_i$$\ob x_i$$a$$\phi$$e(a)=1$$x_i$$e(a)=0$

Skew-simetri grafik menyiratkan bahwa , maka ini adalah tugas yang didefinisikan dengan baik. Selain itu, untuk setiap tepia→bdalam grafik implikasi:$e(\ob a)=\ob{e(a)}$$a\to b$

• Jika tidak dapat dijangkau dari b , maka a ← < b ← , dan a → > b → . Jadi, e ( a ) = 1 menyiratkan e ( b ) = 1 .$a$$b$$a^\ot<b^\ot$$a^\to>b^\to$$e(a)=1$$e(b)=1$

• Kalau tidak, dan b berada dalam komponen yang terhubung sangat kuat, dan a ← = b ← , a → = b → . Jadi, e ( a ) = e ( b ) .$a$$b$$a^\ot=b^\ot$$a^\to=b^\to$$e(a)=e(b)$

Karena itu .$e(\phi)=1$