Masalah keputusan CNF-SAT dapat digambarkan sebagai berikut:
Input: Rumus boolean dalam bentuk normal konjungtif.
Pertanyaan: Apakah ada tugas variabel yang memenuhi ?
Saya sedang mempertimbangkan beberapa pendekatan berbeda untuk memecahkan CNF-SAT dengan mesin Turing dua-tape non-deterministik .
Saya percaya bahwa ada NTM yang memecahkan CNF-SAT dalam langkah .
Pertanyaan: Apakah ada NTM yang memecahkan CNF-SAT dalam langkah ?
Setiap referensi yang relevan dihargai bahkan jika mereka hanya menyediakan pendekatan waktu non-deterministik dekat waktu linear.
time-complexity
sat
turing-machines
np
nondeterminism
Michael Wehar
sumber
sumber
Jawaban:
Ini hanya komentar panjang. Beberapa kali yang lalu saya bertanya (sendiri :-) seberapa cepat NTM multitape yang menerima bahasa NP-complete (cukup dikodekan). Saya datang dengan ide ini:
3-SAT tetap NP-lengkap bahkan jika variabel diwakili dalam unary. Secara khusus kita dapat mengkonversi klausul - kira - dari 3-SAT rumus sewenang-wenang φ pada n variabel dan m klausa dalam urutan karakter lebih alfabet Σ = { + , - , 1 } di mana setiap kejadian variabel diwakili dalam unary:(xi∨¬xj∨xk) φ n m Σ={+,−,1}
Misalnya, dapat dikonversi menjadi:( x2∨ - x 3 ∨ + 4 )
Jadi kita dapat mengonversi rumus 3-SAT dalam string ekuivalen U ( φ i ) yang menyatukan klausa-klausa. Bahasa L U = { U ( φ i ) ∣ φ i ∈ 3 - S A T } adalah NP-complete.φsaya U( φsaya) LU= { U( φsaya) ∣ φsaya∈ 3 - SA T}
2-tape NTM dapat memutuskan apakah string dalam waktu 2 | x | lewat sini.x ∈ LU 2 | x |
Contoh:
Waktu dapat dikurangi menjadi jika kita menambahkan beberapa simbol berlebihan ke representasi klausa:| x |
( menandai akhir formula)+++
Dengan cara ini kepala kedua dapat kembali ke sel paling kiri sementara yang pertama memindai bagian . Menggunakan ++ sebagai pembatas klausa dan +++ sebagai penanda untuk akhir rumus kita bisa menggunakan representasi yang sama untuk rumus CNF dengan jumlah literal per klausa yang sewenang-wenang.0i ++ +++
sumber
Bukan apa yang Anda cari, tetapi untuk NTM 1-tape, jawabannya tampaknya negatif: SAT tidak dapat dipecahkan oleh NTM 1-tape dalam waktu linear non-deterministik.
Menurut makalah ini (Teorema 4.1), kelas bahasa reguler adalah kelas bahasa yang dikenali oleh 1-tape NTM dalam waktu o ( n log ( n ) ) . Jadi, jika ada 1-tape NTM penyelesaian SAT dalam waktu o ( n log ( n ) ) , maka SAT (lebih tepatnya, himpunan rumus yang memuaskan di CNF) akan menjadi bahasa biasa, maka dapat dipecahkan dalam ruang konstan deterministik.REG o(nlog(n)) o(nlog(n))
sumber