  We study the envy-free cake-cutting problem for $d+1$ players with $d$ cuts,
for both the oracle function model and the polynomial time function model. For
the former, we derive a $\theta(({1\over\epsilon})^{d-1})$ time matching bound
for the query complexity of $d+1$ player cake cutting with Lipschitz utilities
for any $d> 1$. When the utility functions are given by a polynomial time
algorithm, we prove the problem to be PPAD-complete.
  For measurable utility functions, we find a fully polynomial-time algorithm
for finding an approximate envy-free allocation of a cake among three people
using two cuts.
