Alternatywne dowody twierdzenia Immermana-Szelepcsenyiego

Immerman i Szelepcsenyi niezależnie okazało się, że . Stosując technikę zliczania indukcyjnego, Borodin i wsp. Udowodnili, że jest zamknięte pod komplementarnością dla . Przed twierdzeniem Reingolda ( ) Nisan i Ta-Shma udowodnili , 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 ? $NL=coNL$ $NL=coNL$

cc.complexity-theory space-bounded

— Shiva Kintali
źródło

Bardzo podobny styl dowodu podają Reinhardt i Allender, „Uczynienie niedeterminizmu jednoznacznym”, aby udowodnić, że wykresy osiągalności st z unikalną ścieżką minimalnej długości między s it można określić w UL \ cap coUL.

— Derrick Stolee

@Derrick: czy mógłbyś opracować odpowiedź?

— András Salamon

@ András: Artykuł Reinhardta i Allendera wykorzystuje indukcyjne liczenie i lemat izolacji, aby pokazać, że NL / poly = UL / poly, tj. W kontekście niejednolitej złożoności, niedeterministyczne obliczenia ograniczone do przestrzeni logicznej mogą być jednoznaczne. Jest to miły, powiązany wynik, ale nie zasługuje na dodanie jako odpowiedź.

— Shiva Kintali

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

Załóżmy, że podano bitów, i musimy uzupełnić każdy bit, aby uzyskać 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 (tj. Na wszystkich wejściach oprócz ). 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.

— V Vinay
źródło

Właśnie dodałem do tego wątku. Liczbę jedynek na wejściu można „odgadnąć” przez wyszukiwanie binarne i dlatego można wykazać, że do zanegowania n bitów potrzebujemy tylko negacji

. Jest to dobrze znane twierdzenie Markowa (dla tych, którzy go nie widzieli, jest to bardzo miłe ćwiczenie). W rzeczywistości, dla funkcji ogólnych

, można ograniczyć liczbę negacji wymaganych do obliczenia

przez log liczby przypadków, gdy

„zmienia znak”, gdy przechodzimy od wejścia wszystkich zer do wejścia wszystkich jedynek [Fischer, I myśleć].

O (\log n)

$O(\log n)$

f

$f$

f

$f$

f

$f$

— Ramprasad

@Vinay, @Ramprasad: Dzięki za piękne spostrzeżenia.

— Shiva Kintali,