Bukti alternatif dari teorema Immerman-Szelepcsenyi

Immerman dan Szelepcsenyi independen membuktikan bahwa . Menggunakan teknik penghitungan induktif mereka, Borodin et al membuktikan bahwa S A C i ditutup dengan komplemen, untuk i > 0 . Sebelum teorema Reingold ( S L = L ), Nisan dan Ta-Shma membuktikan S L = c o S L , menggunakan pengurangan proyeksi seragam logspace. Sebuah makalah tahun 1996 dari Alvarez dan Greenlaw menyatakan "Bukti $NL=coNL$$SAC^i$$i > 0$$SL=L$$SL=coSL$ menggunakan teknik yang mirip dengan Nisan dan Ta-Shma belum tercapai meskipun bukti seperti itu akan sangat menarik ". Saya ingin tahu apakah bukti seperti itu ditemukan dalam 14 tahun terakhir. Apakah ada bukti alternatif lain dari?$NL=coNL$$NL=coNL$

Karena kami sepertinya tidak memiliki jawaban, dapatkah saya memberikan komentar?

Misalkan kita diberi bit, X = x 1 , ⋯ , x n dan kita harus melengkapi setiap bit untuk mendapatkan ¬ x 1 , ⋯ , ¬ x n . Satu-satunya kendala adalah bahwa rangkaian yang melakukannya harus monoton. Kami jelas membutuhkan beberapa informasi tambahan untuk melakukan ini dan ini adalah salah satunya.$n$$X=x_1,\cdots,x_n$$\neg x_1,\cdots, \neg x_n.$

Misalkan adalah jumlah yang ada di input dan entah bagaimana kita memiliki ini sebagai saran. Maka mudah untuk melihat bahwa ¬ x i = T h n - 1 k ( X - x i ) (yaitu, pada semua input kecuali x i ). Tentu saja, konstruksinya monoton.$k$$\neg x_i = Th^{n-1}_{k}(X-x_i)$$x_i$

Dengan konstruksi ini, motivasi untuk penghitungan induktif jelas (setidaknya bagi saya). Patut ditanyakan saran lain apa yang akan berhasil? Saya tidak tahu yang lain. Tapi ini mungkin memegang kunci pertanyaan Anda.