Literatur

GW96

A. Gál and A. Wigderson. Boolean vs. arithmetic complexity classes: randomized reductions. Random Structures and Algorithms, 9:99-111, 1996.

Imm88

N. Immerman. Nondeterministic space is closed under complement. SIAM Journal on Computing, 17:935-938, 1988.

MVV87

K. Mulmuley, U. Vazirani, and V. Vazirani. Matching is as easy as matrix inversion. Combinatorica, 7:105-113, 1987.

Sze88

R. Szelepcsényi. The method of forced enumeration for nondeterministic automata. Acta Informatica, 26:279-284, 1988.

Wig94

A. Wigderson. NL/poly L/poly. In Proc. of the 9th IEEE Structure in Complexity Conference, pages 59-62, 1994.