Provas alternativas do teorema de Immerman-Szelepcsenyi

Immerman e Szelepcsenyi provaram independentemente que . Utilizando sua técnica de contagem indutiva, Borodin et al provaram que o é fechado sob complementação, para . Antes do teorema de Reingold ( S G = G ), Nissan e Ta-Shma provou S L = c O S L , utilizando as reduções de projecção logspace uniformes. Um artigo de 1996 de Alvarez e Greenlaw afirma "Uma prova de N L = c o N LS A C i i > $NL=coNL$$SAC^i$$i > 0$$SL=L$$SL=coSL$$NL=coNL$o uso de técnicas semelhantes às de Nisan e Ta-Shma não foi alcançado, embora tal prova seja muito interessante ". Gostaria de saber se essa prova foi encontrada nos últimos 14 anos. Existem outras provas alternativas de ?$NL=coNL$

Como parece que não temos respostas, posso comentar?

Suponha que recebamos bits, X = x 1 , ⋯ , x n e tenhamos que complementar cada bit para obter ¬ x 1 , ⋯ , ¬ x n . A única restrição é que o circuito que faz isso deve ser monótono. Obviamente, precisamos de algumas informações adicionais para fazer isso e aqui está uma delas.$n$$X=x_1,\cdots,x_n$$\neg x_1,\cdots, \neg x_n.$

Suponha que é o número de unidades na entrada e, de alguma forma, temos isso como conselho. Em seguida, ele é fácil de ver que ¬ x i = T h n - 1 k ( X - X i ) (isto é, em todas as entradas excepto x i ). Obviamente, a construção é monótona.$k$$\neg x_i = Th^{n-1}_{k}(X-x_i)$$x_i$

Com essa construção, a motivação para a contagem indutiva é clara (pelo menos para mim). Vale a pena perguntar que outro conselho funcionaria? Eu não conheço nenhum outro. Mas isso pode ser a chave da sua pergunta.