Теорема Савича: достижимость в неориентированном графе решается с использованием O(log^2n) памяти. Вероятностный алгоритм достижимости в неориентированном графе, использующий O(log n) памяти.