On Equivalent Characterizations of the Polynomial Hierarchy in Abstract Models of Computation

Jeremy C. Kirn, Lucas Meijer, Tillmann Miltzow +1

We investigate machine models similar to Turing machines that are augmented with the operations of a first-order structure $\mathcal{R}$, and we show that under weak conditions on…