Logical Approaches to Computational Barriers

Fast quantifier elimination means P = NP

Speaker:
| Mihai Prunescu |

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 | 2006-06-25 |