The first part is a survey of Poizat's theory about fast elimination of
quantifiers and the P = NP question according to the unit-cost model of
computation, as developped along the book "Les petits cailloux". It
turns out
that for an arbitrary algebraic structure over a finite signature, to have the
property P = NP is equivalent to the fact that its first order theory allows a
fast
quantifier-elimination. We stress the fact that here the word "fast"
should not be understood in the sense of the length of the eliminated formula,
but the length of the eliminating circuit.
The second part is a survey of the structure with fast quantifier elimination
recently constructed by the author and published in The Journal of Symbolic
Logic (1/2006). A structure consisting of infinitely many identical blocks, with
two
independent successor operations and a common predecessor operation, is
expanded with a unary predicate (a colour). If this unary predicate is (1)
generic, (2)
sparse and (3) a truth-predicate for some AE-formal sentences according to the
structure's own first-order theory, then the resulting structure allows
fast quantifier-elimination and has P = NP according to the unit-cost
computation
model. The construction is inductive.