We present two results in structural complexity theory concerned with the following interrelated
topics: computation with postselection/restarting, closed timelike curves (CTCs), and
approximate counting. The first result is a new characterization of the lesser known complexity
class BPP_path in terms of more familiar concepts. Precisely, BPP_path is the class of problems that
can be efficiently solved with a nonadaptive oracle for the Approximate Counting problem. Our
second result is concerned with the computational power conferred by CTCs; or equivalently,
the computational complexity of finding stationary distributions for quantum channels. We
show that any poly(n)-time quantum computation using a CTC of O(log n) qubits may as well
just use a CTC of 1 classical bit. This result essentially amounts to showing that one can find
a stationary distribution for a poly(n)-dimensional quantum channel in PP.

Slightly updated bibliographic discussion of postselection.

We present two results in structural complexity theory concerned with the following interrelated
topics: computation with postselection/restarting, closed timelike curves (CTCs), and
approximate counting. The first result is a new characterization of the lesser known complexity
class BPP_path in terms of more familiar concepts. Precisely, BPP_path is the class of problems that
can be efficiently solved with a nonadaptive oracle for the Approximate Counting problem. Our
second result is concerned with the computational power conferred by CTCs; or equivalently,
the computational complexity of finding stationary distributions for quantum channels. We
show that any poly(n)-time quantum computation using a CTC of O(log n) qubits may as well
just use a CTC of 1 classical bit. This result essentially amounts to showing that one can find
a stationary distribution for a poly(n)-dimensional quantum channel in PP.