  We reconsider the black hole firewall puzzle, emphasizing that quantum
error-correction, computational complexity, and pseudorandomness are crucial
concepts for understanding the black hole interior. We assume that the Hawking
radiation emitted by an old black hole is pseudorandom, meaning that it cannot
be distinguished from a perfectly thermal state by any efficient quantum
computation acting on the radiation alone. We then infer the existence of a
subspace of the radiation system which we interpret as an encoding of the black
hole interior. This encoded interior is entangled with the late outgoing
Hawking quanta emitted by the old black hole, and is inaccessible to
computationally bounded observers who are outside the black hole. Specifically,
efficient operations acting on the radiation, those with quantum computational
complexity polynomial in the entropy of the remaining black hole, commute with
a complete set of logical operators acting on the encoded interior, up to
corrections which are exponentially small in the entropy. Thus, under our
pseudorandomness assumption, the black hole interior is well protected from
exterior observers as long as the remaining black hole is macroscopic. On the
other hand, if the radiation is not pseudorandom, an exterior observer may be
able to create a firewall by applying a polynomial-time quantum computation to
the radiation.
