It states that for any function formula_1,  Toda's theorem is a result that was proven by Seinosuke Toda in his paper "PP is as Hard as the Polynomial-Time Hierarchy" (1991) and was given the 1998 Gödel Prize. The theorem states that the entire polynomial hierarchy PH is contained in PPP; this implies a closely related statement, that PH is contained in P#P. The Immerman–Szelepcsényi theorem was proven independently by Neil Immerman and Róbert Szelepcsényi in 1987, for which they shared the 1995 Gödel Prize. In its general form the theorem states that NSPACE("s"("n")) = co-NSPACE("s"("n")) for any function "s"("n") ≥ log "n". The result is equivalently stated as NL = co-NL; although this is the special case when "s"("n") = log "n", it implies the general theorem by a standard padding argument. The result solved the second LBA problem. Major directions of research in this area include: