Dolne granice wielkości niedeterministycznych obwodów

Wiadomo, że wielkość najmniej -circuits obliczania funkcji parzystości dokładnie równa 3 ( n - 1 ) . Dowód dolnej granicy oparty jest na metodzie eliminacji bramki.$U_2$$3(n-1)$

Ostatnio zauważyłem, że metoda eliminacji bramki działa dobrze również w przypadku niedeterministycznych obwodów , i możemy udowodnić dolną granicę 3 ( n - 1 ) dla wielkości niedeterministycznych obwodów U 2 obliczając funkcję parzystości.$U_2$$3(n-1)$$U_2$

(Oznacza to, że obliczenia niedeterministyczne są bezużyteczne do obliczania parzystości przez obwody i nie mogą zmniejszyć wielkości z 3 ( n - 1 ) . W ten sposób minimalne obwody nie zmieniają się od przypadku deterministycznego.)$U_2$$3(n-1)$

Moje pytania są następujące:

(1) Czy to nowy wynik, czy znany wynik?

(2) Mówiąc bardziej ogólnie, czy istnieją pewne znane wyniki niższych granic wielkości niedeterministycznych obwodów (w tym formuł, obwodów o stałej głębokości itd.) Z nieograniczonymi niedeterministycznymi bitami wejściowymi (lub innymi słowy, nieograniczonym niedeterminizmem) dla wyraźnego funkcjonować?

Dodatkowe wyjaśnienia (27 listopada 2014)

W drugim pytaniu chciałem przede wszystkim wiedzieć, czy jest to pierwsza nietrywialna dolna granica wielkości obwodów niedeterministycznych (w tym formuł, obwodów o stałej głębokości itd.) Z nieograniczonym niedeterminizmem dla określonej funkcji, czy nie. Wiem, że istnieją pewne wyniki, jeśli niedeterminizm jest ograniczony, jak następuje.

[1] Hartmut Klauck: Lower Bounds for Computation with Limited Nondeterminism. Konferencja IEEE na temat złożoności obliczeniowej 1998: 141-

[2] Vikraman Arvind, KV Subrahmanyam, NV Vinodchandran: Złożoność zapytania sprawdzania programu przez obwody o stałej głębokości. ISAAC 1999: 123-132

Częściowa odpowiedź na drugie pytanie:

• wykładnicze dolne granice dla funkcji jawnych dla dowolnej klasy, która zawiera 3-CNF, nie przekładają się na wykładnicze dolne granice dla nieograniczonego niedeterminizmu, ponieważ można przekształcić dowolny obwód wielkości w niedeterministyczny 3-CNF wielkości O ( S ) z niedeterminizmem S ,$S$$O(S)$$S$
• nawet jeśli chcesz, aby niedeterminizm był mniejszy niż S, jest to nadal wykonalne, jeśli funkcja jest obliczana na podstawie wzoru (na przykład parzystości), ponieważ można podzielić tę formułę rozmiaru S na, powiedzmy, S / 100 elementów wprowadzających S / 100 nowych zmiennych, a wynikowy wzór będzie miał rozmiar O ( S ) (chociaż stała w O $B_2$$S$$S/100$$S/100$$O(S)$ będzie duża),$O()$
• $2^{n^{1/d}}$$n^{1/d}$

Częściowa odpowiedź na pierwsze pytanie:

• nie wiadomo mi :) ciekawym byłoby zobaczyć dowód (w szczególności, jak można zastąpić wartości zmiennymi egzystencjalnymi).