Preuves alternatives du théorème d'Immerman-Szelepcsenyi

Immerman et Szelepcsenyi indépendamment prouvé que . En utilisant leur technique de comptage inductif, Borodin et al ont prouvé que S A C i est fermé sous complémentation, pour i > 0 . Avant le théorème de Reingold ( S L = L ), Nisan et Ta-Shma ont prouvé S L = c o S L , en utilisant des réductions de projection uniformes dans l'espace logarithmique. Un article publié en 1996 par Alvarez et Greenlaw déclare «Une preuve de $NL=coNL$$SAC^i$$i > 0$$SL=L$$SL=coSL$ utilisant des techniques similaires à celles de Nisan et Ta-Shma n'a pas été atteint bien qu'une telle preuve serait très intéressante ". Je me demande si une telle preuve a été trouvée au cours des 14 dernières années. Existe-t-il d'autres preuves alternatives de N L = c o N L ?$NL=coNL$$NL=coNL$

Puisque nous ne semblons pas avoir de réponses, puis-je faire un commentaire?

$n$$X=x_1,\cdots,x_n$$\neg x_1,\cdots, \neg x_n.$

$k$$\neg x_i = Th^{n-1}_{k}(X-x_i)$$x_i$

Avec cette construction, la motivation pour le comptage inductif est claire (du moins pour moi). Il vaut la peine de demander quels autres conseils fonctionneraient? Je n'en connais pas d'autre. Mais cela peut détenir la clé de votre question.