On finite structures without an order, the inflationary and the partial fixed-point logics define the same problems if and only if PTIME = PSPACE. If the classes are equal, an order-free partial definition is relativized to an order, captured in PSPACE = PTIME, and brought back. Conversely, an order-free FO(PFP) computation with $k$ variables is invariant under the equivalence of $k$-tuples by the $k$-pebble game; it therefore runs on the structure of the equivalence classes, which carries a linear order definable by an inflationary induction, and there the equality of the logics on ordered structures applies. The proof follows the machine-free route of Dawar, Lindell and Weinstein and of Ebbinghaus and Flum.