Computability in Europe 2006
Logical Approaches to Computational Barriers
Special Session Talk:
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.
|websites: Arnold Beckmann||
Warning: date(): It is not safe to rely on the system's timezone settings. You are *required* to use the date.timezone setting or the date_default_timezone_set() function. In case you used any of those methods and you are still getting this warning, you most likely misspelled the timezone identifier. We selected the timezone 'UTC' for now, but please set date.timezone to select your timezone. in /srv/www/htdocs-cs/cie06/conf-code.php on line 135