test FOO test
Computability in Europe 2006
Logical Approaches to Computational Barriers
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
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
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
independent successor operations and a common predecessor operation, is
expanded with a unary predicate (a colour). If this unary predicate is (1)
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
model. The construction is inductive.
websites: Arnold Beckmann