We explore new directions in simulating complex computations with low space, building on the work of Williams [STOC'25] and Cook-Mertz [STOC'24, SICOMP'25]. We define and study a strengthened version of the parallel external memory model, in which there are $P$ processors each with private internal memory $M$, all of which have shared access to an external memory. Like the standard external memory model, a processor is charged one step when it swaps up to $M$ bits of its internal memory with the external memory; unlike the usual external memory model, each processor also has free access to the input at no cost, and may read any subset of M bits of external memory (not just a contiguous block) in a single I/O step.
We extend the reduction of Williams for multitape Turing machines to this vastly more general model, giving three main applications.
1. We show that the $P$-complete problem {\sc Lex First 2sat}, where even the best-known RAM algorithm runs in $O(n^{\omega})\leq O(n^{2.372})$ time on instances with $\Theta(n^2)$ clauses, nevertheless has an $\tilde{O}(\sqrt{n})$-space algorithm for $n$-variable instances. For dense instances with $\Theta(n^2)$ clauses, our space usage is less than the \emph{fourth root} of the best-known RAM running time.
2. We show that every \emph{unbounded} fan-in circuit of $n$ gates over the basis $\{$NOT, AND, OR, XOR$\}$ can be evaluated on any given input in only $O(\sqrt{n \log n})$ space. That is, the space usage is nearly a fourth root of the running time for dense circuits with $\Theta(n^2)$ wires. This result generalizes a space-efficient simulation of Shalunov for bounded fan-in circuits.
3. We consider the problem of simulating a $d$-dimensional cellular automaton, where the value of each cell is determined by its immediate neighbors. We show how to simulate $t$ time steps of a cellular automaton in only $O((t\log t)^{1-1/(d+1)})$ space. By an old theorem of Cook [1966], our space-efficient simulation of one-dimensional cellular automata yields another generalization of Williams' simulation of multitape time.
