Alternatywne dowody twierdzenia Immermana-Szelepcsenyiego

Immerman i Szelepcsenyi niezależnie okazało się, że . Stosując technikę zliczania indukcyjnego, Borodin i wsp. Udowodnili, że S A C i jest zamknięte pod komplementarnością dla i > 0 . Przed twierdzeniem Reingolda ( S L = L ) Nisan i Ta-Shma udowodnili S L = c o S L , stosując redukcje równomiernego rzutowania przestrzeni logicznej. Artykuł Alvareza i Greenlawa z 1996 r. Stwierdza: „Dowód $NL=coNL$$SAC^i$$i > 0$$SL=L$$SL=coSL$ przy użyciu technik podobnych do Nisana i Ta-Shmy nie został osiągnięty, chociaż taki dowód byłby bardzo interesujący ". Zastanawiam się, czy taki dowód został znaleziony w ciągu ostatnich 14 lat. Czy są jakieś inne alternatywne dowody z N L = c o N L ?$NL=coNL$$NL=coNL$

Ponieważ wydaje się, że nie mamy żadnych odpowiedzi, czy mogę coś skomentować?

Załóżmy, że podano bitów, X = x 1 , ⋯ , x n i musimy uzupełnić każdy bit, aby uzyskać ¬ x 1 , ⋯ , ¬ x n . Jedynym ograniczeniem jest to, że obwód, który to robi, powinien być monotoniczny. Potrzebujemy oczywiście dodatkowych informacji, a oto jedna z nich.$n$$X=x_1,\cdots,x_n$$\neg x_1,\cdots, \neg x_n.$

Załóżmy, że jest liczbą wejściową i jakoś mamy to jako wskazówkę. Wtedy łatwo zauważyć, że ¬ x i = T h n - 1 k ( X - x i ) (tj. Na wszystkich wejściach oprócz x i ). Oczywiście konstrukcja jest monotonna.$k$$\neg x_i = Th^{n-1}_{k}(X-x_i)$$x_i$

Dzięki tej konstrukcji motywacja do liczenia indukcyjnego jest jasna (przynajmniej dla mnie). Warto zapytać, jakie inne porady by działały? Nie znam żadnego innego. Ale to może mieć klucz do twojego pytania.