Does every complete theory admit quantifier elimination? Does every complete theory admit quantifier elimination? I know that at least in some simple cases the reverse is true; such as some reducts of number theory.Thanks
 A: Let $G=(V,E)$ be a countable graph such that there exists a point $a\in{V}$ such that for all $b\in{V}$, $(a,b)\notin{E}$ and $E\neq{\emptyset}$.
Let $L=\{R\}$, where $R$ is a binary relation. Let $\mathcal{M}$ be the model of $G$ in the language $L$. Put $T=Th(\mathcal{M}),$ we claim that $T$ has no quantifier elimination.
Suppose this is not so, then all maps $f:N\rightarrow M$ such that $N$ is a finite subset of $M$; and thus a substructure of $\mathcal M$ as $L$ is a relational language, and $f:N\rightarrow Im(f)$ is an isomorphim, are elementary embeddings into $\mathcal M$. 
But as $E\neq\emptyset$, there are $b,c\in V$ such that $(b,c)\in E$, then the map $f=\{(a,b)\}$ is an isomorphism between the substructures $\{a\}$ and $\{b\}$, however $f:\{a\}\rightarrow M$ is not  elementary.
A: No, not every complete theory has quantifier elimination. 
Take $\mathcal{L} = \{U\}$ where $U$ is a unary function symbol. And take the structure $\mathbf{N} = (\mathbb{N}, S)$ where $S$ is the successor function. 
Then of course $\operatorname{Th}(\mathbf{N})$ is complete. But the only atomic formulas in one variable are of the form $S^n(x) = S^m(x)$ for some $n,m \in\mathbb{N}$. And because $S$ is one to one this is the same as $S^k(x) = x$ for some $k \in\mathbb{N}$. 
For $k = 0$ this defines $\mathbb{N}$ and for $k \geq 1$ this defines $\varnothing$. 
Thus every quanitifer free formula in one variable defines either $\mathbb{N}$ or $\varnothing$. 
However, the set $\{0\}$ is definable in one free variable by $\forall y S(y) \neq x$. 
So $\operatorname{Th}(\mathbf{N})$ cannot have quantifier elimination.
A: In another post I've given an example of how the theory of real closed fields in the language $(0,1,+,\cdot)$ does not have q.e. (even though it is model complete).
As for the other question, using the characterization of q.e. by substructural completeness (which I have, again, explained in that post) you can see that if a theory has q.e. AND has a constant symbol AND decides all quantifier-free sentences (that is, formulas without variables), then it is complete (which probably covers your reducts of number theory, as they would likely have a symbol for $0$ or $1$).
Without constants it need not be true. Consider the language $\{P\}$ with one unary predicate, and the theory which says that the model is infinite and that all its elements agree on $P$.  It clearly isn't complete, but has q.e. (which is easy to check directly, or by substructural completeness).
