  We propose a new generalisation of Cayley automatic groups, varying the time
complexity of computing multiplication, and language complexity of the normal
form representatives. We first consider groups which have normal form language
in the class $\mathcal C$ and multiplication by generators computable in linear
time on a certain restricted Turing machine model (position-faithful one-tape).
We show that many of the algorithmic properties of automatic groups are
preserved (quadratic time word problem), prove various closure properties, and
show that the class is quite large; for example it includes all virtually
polycyclic groups. We then generalise to groups which have normal form language
in the class $\mathcal C$ and multiplication by generators computable in
polynomial time on a (standard) Turing machine. Of particular interest is when
$\mathcal C= \mathrm{REG}$ (the class of regular languages). We prove that
$\mathrm{REG}$-Cayley polynomial-time computable groups includes all finitely
generated nilpotent groups, the wreath product $\mathbb Z_2 \wr \mathbb Z^2$,
and Thompson's group $F$.
